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 条评论
登录 后参与评论

相关文章

来自专栏Java3y

TreeMap就这么简单【源码剖析】

2025
来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

1474
来自专栏朱慕之的博客

基础算法

0.创建类 BinaryTreeNode 1.创建方法:传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法,将根节点的左...

671
来自专栏java学习

来测试一下你对数据结构中的栈和队列的了解有多少?

选择题 1.向一个栈顶指针为top的链栈中插入一个结点s,执行( )。 A.top.next=s; B.s.next=top.next ;top.next=s;...

6019
来自专栏移动端开发

用OC和Swift一起说说二叉树

前言:    一:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subt...

2255
来自专栏小樱的经验随笔

51 Nod 1008 N的阶乘 mod P【Java大数乱搞】

1008 N的阶乘 mod P 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 输入N和P(P为质数),求N! Mod P ...

2666
来自专栏LeetCode

LeetCode 114. Flatten Binary Tree to Linked List

关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。

210
来自专栏移动端开发

用OC和Swift一起说说二叉树

   一:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)...

945
来自专栏desperate633

LeetCode 144. Binary Tree Preorder Traversal题目分析代码

Given a binary tree, return the preorder traversal of its nodes' values. For ex...

922
来自专栏郭耀华‘s Blog

LeetCode第六天

第六天 30.(219) Contains Duplicate II ? JAVA class Solution { public boolean co...

2757

扫码关注云+社区