Finding the nearest common ancestor of binary tree by recursion

236. The nearest common ancestor of a binary tree

difficulty ： secondary

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

Baidu Encyclopedia The definition of the most recent common ancestor in 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 ）.

Ideas

If you can't understand this question, you can have a look first Find the nearest common ancestor of binary search tree

There are three situations

• Both nodes are smaller than the current node , Are all on the left subtree of the current node
• Both nodes are larger than the current node , Are all on the right subtree of the current node
• One is larger than the current node （ be equal to ）, One is smaller than the current node （ be equal to ）, Then the current node is the nearest common ancestor of the two nodes

But if it is implemented, we cannot judge whether it is on the left or right of the current node according to the value of the current node

So we can only traverse all subtrees of the current node , See if you can find at least one node on its left or right

• If the current node is equal to one of the nodes , Then return directly
• If there is a node on the left side and a node on the right side , It means that the current node is the nearest public child node
• If both are on one side , Then the nearest one must be at a node on that side

package cn.edu.xjtu.carlWay.tree.commonAncestor;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 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 . * <p> *  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 ）.” * <p> * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/ */
public class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        if (root == null) {
    
            return null;
        }
        //  The node and its subtree must contain at least one node 
        if (root.val == p.val || root.val == q.val) {
    
            return root;
        }

        //  Judge whether the left and right subtrees of the current node contain at least one node 
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        if (leftNode != null && rightNode != null) {
    
            //  If both the left subtree and the right subtree contain a node , It means that the current node is the nearest public child node 
            return root;
        } else {
    
            //  Otherwise, the two must not do null The other side of the 
            return leftNode == null ? rightNode : leftNode;
        }
    }
}