Leetcode exercise -- two questions about the nearest common ancestor of binary trees

1. The nearest common ancestor of a binary search tree

1.1 Title Description

235. The nearest common ancestor of a binary search tree

Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

for example , Given the following binary search tree :  root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

 Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 Output : 6 
 explain :  node  2  And nodes  8  The most recent public ancestor of  6.

Example 2:

 Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
 Output : 2
 explain :  node  2  And nodes  4  The most recent public ancestor of  2,  Because by definition, the nearest common ancestor node can be the node itself .

1.2 Problem solving ideas and codes

1.2.1 Their thinking

This problem needs to grasp the key ： Search binary trees , Then the problem is relatively simple , We use recursion to traverse binary trees . When we traverse a node, for a given two nodes p and q There are only three situations ：

1. p and q The value of is smaller than the current node , namely p and q Are on the left subtree of the current node , At this time, we will go left Continue traversal on ;
2. p and q The value of is larger than the current node , namely p and q Are on the right subtree of the current node , At this time, we will go right Continue traversal on ;
3. p Larger than the current node q Smaller than the current node or p Smaller than the current node q Larger than the current node , Is this time p and q On the left and right subtrees of the current node , Then the current node is p and q The common ancestor of

1.2.2 Code

class Solution {
    
    TreeNode node = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        process(root,p,q);
        return node;
    }

    public void process(TreeNode root, TreeNode p, TreeNode q) {
    
        if (root == null) {
    
            return;
        }
        if (root.val < p.val && root.val < q.val) {
    
            process(root.right, p, q);
        } else if (root.val > p.val && root.val > q.val) {
    
            process(root.left, p, q);
        } else {
    
            node = root;
            return;
        }
    }
}

1.3 test result

Pass the test

2. The nearest common ancestor of a binary tree

2.1 Title Description

236. The nearest common ancestor of a binary tree

Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Example 1：

 Input ：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 Output ：3
 explain ： node  5  And nodes  1  The most recent public ancestor of is the node  3 .

Example 2：

 Input ：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 Output ：5
 explain ： node  5  And nodes  4  The most recent public ancestor of is the node  5 . Because by definition, the nearest common ancestor node can be the node itself .

Example 3：

 Input ：root = [1,2], p = 1, q = 2
 Output ：1

2.2 Problem solving ideas and codes

2.2.1 Their thinking

The difference when encountering a problem is , This problem is an ordinary binary tree , There is no size relationship on the node , You can't use the above ideas . Then we can recursively traverse the whole binary tree , And use map Store the mapping between the current node and the parent node . After traversing the binary tree, you can start from map In order to get p Nodes start to traverse upward in turn , And use the collection to store the traversal path . And then from map In order to get q Nodes and traverse upward in turn , When in p Found in the path set of q When traversing up the node , Then we found the common ancestor . From p Nodes and q Node up convenience , When the first same node is encountered , Is the common ancestor .

2.2.2 Code

class Solution {
    
    Map<TreeNode, TreeNode> map = new HashMap<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        process(null, root);
        Set<TreeNode> set = new HashSet<>();
        while (p != null) {
    
            set.add(p);
            p = map.get(p);
        }
        while (!set.contains(q)){
    
            q = map.get(q);
        }
        return q;
    }

    public void process(TreeNode parent, TreeNode node) {
    
        if (node == null) {
    
            return;
        }
        if (parent != null) {
    
            map.put(node, parent);
        }
        process(node, node.left);
        process(node, node.right);
    }
}

2.3 test result

Pass the test

3. summary

• It is relatively simple to search the common ancestor of binary search tree and directly traverse the binary tree , If p Nodes and q The nodes are on the left and right subtrees of the current node , Then the current node is the common ancestor
• The common ancestor search of ordinary binary search tree is from p Nodes and q Node network traversal , When the two paths meet for the first time , Is the common ancestor