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

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

题目:

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

思路:

后续遍历+DFS:具体思路参照了题解中的解析

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

代码:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //先判断根节点本身是不公共点,如果是公共点,就是公共祖先
        if(!root || root == p || root == q) return root; 
        //否则,判断左支树返回值
        auto left = lowestCommonAncestor(root->left, p, q);
        //判断右支树返回值。
        auto right = lowestCommonAncestor(root->right, p, q);
        //如果左子树返回值为空,那就返回右子树返回值,因为答案肯定存在
        if(!left) return right;
        if(!right) return left;

        //如果都存在,则返回根节点,为公共祖先
        return root;
    }
};

Rank:

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

Tips:

就这,此题做的很敷衍,今天学习兴致不高。感觉差点意思,还是要再总结一下二叉树的基础知识点,然后再猛刷题。

上一篇:leetcode二叉树最近公共祖先236


下一篇:236. 二叉树的最近公共祖先