二叉树——236. 二叉树的最近公共祖先
题目:
思路:
后续遍历+DFS:具体思路参照了题解中的解析
代码:
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:
Tips:
就这,此题做的很敷衍,今天学习兴致不高。感觉差点意思,还是要再总结一下二叉树的基础知识点,然后再猛刷题。