LeetCode #236：Lowest Common Ancestor Of A Binary Tree(二叉树的最近公共祖先)

题目描述

本题的思路是采用后续遍历（自底向上）来寻找答案。在后续遍历中，当一个结点的左子树和右子树分别找到 p、q 时，该结点就是答案。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
            return NULL;

        if(root == p || root == q) // 当某个分支中找到了p或q时，返回该结点
            return root;
        
        auto l = lowestCommonAncestor(root->left, p, q);
        auto r = lowestCommonAncestor(root->right, p, q);

        if(l && r) // 左右分支分别找到了p、q，表明找到了答案，但不会立即返回，而是要逐级传递上去直到树根
            return root;
        else if(l == NULL && r) // 若一个分支返回NULL，说明结果会在另一个分支上一级一级传递到树根
            return r;
        else if(l && r == NULL)
            return l;
        else // l == NULL && r == NULL
            return NULL;
    }
};

本题中即使在某个分支已经找到结果，我们依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的 left和 right）做逻辑判断。