LWC 62:742. Closest Leaf in a Binary Tree

LWC 62:742. Closest Leaf in a Binary Tree

传送门:742. Closest Leaf in a Binary Tree

Problem:

Given a binary tree where every node has a unique value, and a target key k, find the closest leaf node to target k in the tree. A node is called a leaf if it has no children. In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input: root = [1, 3, 2], k = 1 Diagram of binary tree: 1 / \ 3 2 Output: 2 (or 3) Explanation: Either 2 or 3 is the closest leaf node to 1.

Example 2:

Input: root = 1, k = 1 Output: 1 Explanation: The closest leaf node is the root node itself.

Example 3:

Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2 Diagram of binary tree: 1 / \ 2 3 / 4 / 5 / 6 Output: 3 Explanation: The leaf node with value 3 (and not the leaf node with value 6) is closest to the node with value 2.

Note:

root represents a binary tree with at least 1 node and at most 1000 nodes.

Every node has a unique node.val in range [1, 1000].

There exists some node in the given binary tree for which node.val == k.

思路: 给定某个结点k,求离k最近的叶子结点是谁。实际上可以把树看作为无向图,所以问题就转化为求k到任意结点的最短距离。当然此处答案在叶子结点中更新即可。还需注意:在树构成的无向图中,每两个结点之间的路径只会存在一条,所以才无脑递归或者无脑bfs。具体怎么无脑参看代码。

Java 递归版本:

    List<Integer>[]  graph;
    List<Integer> leaves;
    int[] dist;

    void add(int from, int to) {
        graph[from].add(to);
        graph[to].add(from);
    }

    void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null) leaves.add(root.val);

        if (root.left != null) add(root.val, root.left.val);
        if (root.right != null) add(root.val, root.right.val);

        dfs(root.left);
        dfs(root.right);
    }

    void efs(int x, int p, int d) {
        dist[x] = d;
        for (int to : graph[x]) {
            if (to != p) efs(to, x, d + 1);
        }
    }


    public int findClosestLeaf(TreeNode root, int k) {
        int INF = 0x3f3f3f3f;
        graph  = new ArrayList[1016];
        leaves = new ArrayList<>();
        dist   = new int[1016];
        Arrays.fill(dist, INF);

        for (int i = 0; i < 1016; ++i) graph[i] = new ArrayList<>();

        // 树转无向图,并求得叶子结点
        dfs(root);
        // 无脑k出发到其他所有结点的最短路径
        efs(k, -1, 0);

        int min = INF;
        int minNode = -1;

        for (int leaf : leaves) {
            if (dist[leaf] < min) {
                min = dist[leaf];
                minNode = leaf;
            }
        }

        return minNode;
    }

Python 广搜版本:

    def findClosestLeaf(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        leaves = set()
        graph  = [[] for _ in xrange(1016)]
        def traverse(root):
            if not root: return
            if not root.left and not root.right: leaves.add(root.val)
            if root.left:
                graph[root.val].append(root.left.val)
                graph[root.left.val].append(root.val)
            if root.right:
                graph[root.val].append(root.right.val)
                graph[root.right.val].append(root.val)

            traverse(root.left)
            traverse(root.right)

        traverse(root)
        dist = [0] * 1016

        pq = []
        pq.append((0, k))
        dist[k] = 0
        vis = set()
        vis.add(k)

        while len(pq):
            cur = pq.pop(0)
            if cur[1] in leaves: return cur[1]
            for to in graph[cur[1]]:
                if to not in vis:
                    dist[to] = cur[0] + 1
                    pq.append((cur[0] + 1, to))
                    vis.add(to)   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据处理

二叉搜索树

903
来自专栏desperate633

LintCode 平衡二叉树题目分析代码

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。

552
来自专栏calmound

110Balanced Binary Tree

问题:判断二叉树是否为平衡二叉树 分析:树上的任意结点的左右子树高度差不超过1,则为平衡二叉树。          搜索递归,记录i结点的左子树高度h1和右子树...

2716
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树1

二叉排序树,是一种规整的二叉树。每个节点的左子树都小于他,每个节点的右子树都大于他。 二叉树的遍历: void InOrderTree(BTree *b){ ...

1709
来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

591
来自专栏武培轩的专栏

剑指Offer-二叉搜索树与双向链表

题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 思路一: 由于要求链表是有序...

2563
来自专栏郭耀华‘s Blog

剑指offer第五天

28.数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2...

2605
来自专栏desperate633

LintCode 子数组之和题目分析代码

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

462
来自专栏数据结构与算法

2879 堆的判断

2879 堆的判断 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 堆是一种常用...

3028
来自专栏机器学习入门

LWC 58:724. Find Pivot Index

LWC 58:724. Find Pivot Index 传送门:724. Find Pivot Index Problem: Given an array ...

1778

扫码关注云+社区