Leetcode——236. 二叉树的最近公共祖先

概述

236. 二叉树的最近公共祖先

分析

• 题目要求找树中等两个节点的最近公共祖先，容易想到应该从下往上查找，进而想到使用后序遍历

• 通过后序遍历，可以从树的下面开始遍历一个结点的左右子树，如果左右子树分别有指定的结点的话，则该节点一定是最低的公共祖先

  因为后序一定是从下面开始的，如果左右子树中有指定结点的话，那么一定是第一次出现

思路

如何确定左右子树是否拥有指定的结点？

• 遍历过程中，判断遍历的节点是否和指定结点相同，如果相同，则返回该结点

代码

class Solution {
    
public:
    // 4. 确定递归函数返回值
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    		// 1. 确定递归函数
        // 3. 确定终止条件。 如果节点==p、q则说明找到了；如果节点=nullptr，则遍历结束
        if (root == p || root == q || root = nullptr) {
    	// 如果找到指定的节点 or 为空节点
            return root;
        }

        // 1. 确定单层递归逻辑————后序遍历
        TreeNode *lNode=lowestCommonAncestor(root -> left, p, q);		
        TreeNode *rNode=lowestCommonAncestor(root -> right, p, q);

        // 2. 明确递归函数的作用
        // lowestCommonAncestor的作用：判断在以root节点为根的子树中，是否拥有p、q指向的结点
   
        if (lNode != nullptr && rNode != nullptr)	// 如果在左右子树中，
            return root;
        else if(lNode == nullptr) {
      //两个都在右子树
            return rNode;
        }
        else {
     //两个都在左子树里面
            return lNode;
        }
        
        return nullptr;
    }
};