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

相关文章

来自专栏小樱的经验随笔

Gym 100952E&&2015 HIAST Collegiate Programming Contest E. Arrange Teams【DFS+剪枝】

E. Arrange Teams time limit per test:2 seconds memory limit per test:64 megabyte...

2606
来自专栏机器学习入门

LWC 63:748. Shortest Completing Word

LWC 63:748. Shortest Completing Word 传送门:748. Shortest Completing Word Problem: ...

1939
来自专栏ml

HDUOJ---1195Open the Lock

Open the Lock Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

2666
来自专栏算法修养

HDU 4605 Magic Ball Game(可持续化线段树,树状数组,离散化)

Magic Ball Game Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/...

2836
来自专栏算法修养

HDU 1403 Eight&POJ 1077(康拖,A* ,BFS,双广)

Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Ja...

2827
来自专栏机器学习入门

LWC 63: 749. Contain Virus

Problem: A virus is spreading rapidly, and your task is to quarantine the infec...

1878
来自专栏WD学习记录

LeetCode Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

711
来自专栏Bingo的深度学习杂货店

Q28 Implement strStr()

Implement strStr(). Return the index of the first occurrence of needle in haysta...

31510
来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

1909
来自专栏郭耀华‘s Blog

LeetCode第四天

leetcode 第四天 2018年1月4日 15.(628)Maximum Product of Three Numbers ? JAVA class Sol...

2985

扫码关注云+社区