Leetcode——236. The nearest common ancestor of binary tree

summary

236. The nearest common ancestor of a binary tree

analysis

• The problem requires finding the nearest common ancestor of two nodes in the tree , It's easy to think of finding it from the bottom up , Then I think of using post order traversal

• Through post order traversal , You can traverse the left and right subtrees of a node from the bottom of the tree , If the left and right subtrees have specified nodes respectively , Then the node must be the lowest common ancestor

  Because the sequence must start from the following , If there are specified nodes in the left and right subtrees , Then it must be the first time

Ideas

How to determine whether the left and right subtrees have specified nodes ？

• During traversal , Judge whether the traversal node is the same as the specified node , If the same , The node is returned

Code

class Solution {
    
public:
    // 4.  Determine the return value of recursive function 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    		// 1.  Determine the recursive function 
        // 3.  Determine termination conditions .  If node ==p、q It says it found it ; If node =nullptr, Then the traversal ends 
        if (root == p || root == q || root = nullptr) {
    	//  If the specified node is found  or  Is an empty node 
            return root;
        }

        // 1.  Determine single level recursive logic ———— After the sequence traversal 
        TreeNode *lNode=lowestCommonAncestor(root -> left, p, q);		
        TreeNode *rNode=lowestCommonAncestor(root -> right, p, q);

        // 2.  Clarify the role of recursive functions 
        // lowestCommonAncestor The role of ： Judgment is based on root In the subtree whose node is the root , Owned or not p、q Pointed node 
   
        if (lNode != nullptr && rNode != nullptr)	//  If in the left and right subtrees ,
            return root;
        else if(lNode == nullptr) {
      // Both are in the right subtree 
            return rNode;
        }
        else {
     // Both are in the left subtree 
            return lNode;
        }
        
        return nullptr;
    }
};