Sword finger offer 68 - ii The nearest common ancestor of binary tree

The finger of the sword Offer 68 - II. The nearest common ancestor of a binary tree

subject

  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, 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 ）.”

Ideas

• If P and Q All are root Left and right nodes of , that root It's the nearest public ancestor we're looking for
• If P and Q All are root The left node , Then the return lowestCommonAncestor(root.left,p,q)
• If P and Q All are root The right of the node , Then the return lowestCommonAncestor(root.right,p,q)

Boundary conditions ：

• If root = null That means we can't find , If root = p perhaps root = q, return root
• If the left tree is not found , Recursive functions return null, prove p and q They are all tested at the same time , Then look in the right subtree
• If the right subtree is not found , Recursive functions return null, prove p and q They are all tested at the same time , Then look in the left subtree

Code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if(root == null || root == p || root == q)
        {
    
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        if(leftNode == null)
        {
    
            return rightNode;
        }

        if(rightNode == null)
        {
    
            return leftNode;
        }

        return root;
    }
}