Yyds dry inventory solution sword finger offer: find the nearest common ancestor of two nodes in the binary tree

1. sketch ：

describe

Given a binary tree ( Make sure it's not empty ) And the two nodes on the tree val value o1  and  o2, Please find o1  and  o2  The nearest common ancestor node of . Data range ： The number of nodes in the tree meets   , Node values val Satisfaction interval [0,n) requirement ： Time complexity   notes ： This problem ensures that each node in the binary tree is val Values are different . For example, when entering {3,5,1,6,2,0,8,#,#,7,4},5,1 when , Binary tree {3,5,1,6,2,0,8,#,#,7,4} As shown in the figure below ： So the node value is 5 And node values are 1 The node value of the nearest common ancestor node of the node is 3, So the corresponding output is 3. The node itself can be regarded as its own ancestor

Example 1

Input ：

Log in and copy

      
      

       
       {3,5,1,6,2,0,8,#,#,7,4},5,1
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       3
      
      
      
      

       
       
1.
      
      

Example 2

Input ：

Log in and copy

      
      

       
       {3,5,1,6,2,0,8,#,#,7,4},2,7
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       2
      
      
      
      

       
       
1.
      
      

2. Code implementation ：

Log in and copy

      
      

       
       import java.util.*;
       
       

       
       
/*
       
       
 * public class TreeNode {
       
       
 *   int val = 0;
       
       
 *   TreeNode left = null;
       
       
 *   TreeNode right = null;
       
       
 * }
       
       
 */
       
       

       
       
public class Solution {
       
       
    /**
       
       
     * 
       
       
     * @param root TreeNode class  
       
       
     * @param o1 int integer  
       
       
     * @param o2 int integer  
       
       
     * @return int integer 
       
       
     */
       
       
        public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
       
       
        return helper(root, o1, o2).val;
       
       
    }
       
       

       
       
    public TreeNode helper(TreeNode root, int o1, int o2) {
       
       
        if (root == null || root.val == o1 || root.val == o2)
       
       
            return root;
       
       
        TreeNode left = helper(root.left, o1, o2);
       
       
        TreeNode right = helper(root.right, o1, o2);
       
       
        // If left It's empty , Show that these two nodes are in root On the right subtree of the node , We just need to return the result of the right subtree 
       
       
        if (left == null)
       
       
            return right;
       
       
        // ditto 
       
       
        if (right == null)
       
       
            return left;
       
       
        // If left and right It's not empty. , Show that one of these two nodes is root One on the left tree of root On the right subtree ,
       
       
        // We just have to go back cur The node can be .
       
       
        return root;
       
       
    }
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.