This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact

describe

Given the root of a binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

  • The node of a binary tree is a leaf if and only if it has no children
  • The depth of the root of the tree is 0. if the depth of a node is d, the depth of each of its children is d + 1.
  • The lowest common ancestor of a set S of nodes, is the node A with the largest depth such that every node in S is in the subtree with root A.

Note: This question is the same as 865: leetcode.com/problems/sm…

Example 1:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4] Output:,7,4 [2] Explanation: We return the node with value 2, colored in yellow in the diagram. The nodes coloured in blue are the deepest leaf-nodes of the tree. Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.Copy the code

Example 2:

Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree, and it's the lca of itself.
Copy the code

Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest leaf node in the tree is 2, the lca of one node is itself.
Copy the code

Note:

The number of nodes in the tree will be in the range [1, 1000].
0 <= Node.val <= 1000
The values of the nodes in the tree are unique.
Copy the code

parsing

(27) The lowest common ancestor of a binary tree is the lowest common ancestor. Based on the title description and several examples, we can conclude that there are three results:

  • If there is only the root node, it is itself the lowest common ancestor node, as in example 2.
  • If two of the deepest siblings have the same depth, then their common parent is the lowest common ancestor, as in example 1.
  • If only one leaf node has the deepest depth in the whole tree, then this node is the lowest common ancestor node, as in Example 3.

So using the recursive idea, define the recursive function DFS, each call DFS returns the lowest common ancestor node reference of the current depth and the current depth.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def lcaDeepestLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def dfs(root):
            if not root:
                return None, 0

            L, L_d = dfs(root.left)
            R, R_d = dfs(root.right)

            if L_d == R_d:
                return root, L_d+1 
            elif L_d > R_d:
                return L, L_d+1
            else:
                return R, R_d+1

        return dfs(root)[0]
        	      
		
Copy the code

The results

Runtime: 10 ms, faster than 66.99% in the linked subsurface submission to the piver. Memory Usage: 4 MB, less than 7.77% of Python online submissions for closed Common Ancestor of melancholy Leaves.Copy the code

parsing

I could write it a different way. Same principle

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def lcaDeepestLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def dfs(root, d):
            if not root: return None,d

            L, L_d = dfs(root.left, d+1)        
            R, R_d = dfs(root.right, d+1)

            if L_d == R_d:
                return root, L_d
            elif L_d > R_d:
                return L, L_d
            else:
                return R, R_d
        return dfs(root, 0)[0]
Copy the code

The results

Runtime: 10 MS, faster than 91.26% for each node in the Python online submission. Memory Usage: 4 MB, less than 27.18% of Python online submissions for closed Common Ancestor of melancholy Leaves.Copy the code

Original link: leetcode.com/problems/lo…

Your support is my biggest motivation