题目链接

题意

如题目。附上一张二叉树的图片。
剑指offer68-II 二叉树的最近公共祖先 - 图1

题解

这里的是普通二叉树，不同于二叉搜索树有特定的性质。固这里需要思考新的搜索策略。
这里采用后序遍历的搜索策略：

  • 即对于整棵树，从下往上搜索，递归搜索。
  • 对于每一个节点，先去搜索它的左右子树。左右子树根据搜索情况，返回各自搜索情况。然后根据其左右子树的搜索情况，给出其回溯的返回结果。
  • 最终的结果，由回溯到整棵树根节点时，根据其搜索情况获得。

那么当前子树根节点的搜索情况有如下几种：

  • 左子树搜索返回为空，右子树搜索返回也为空。此时说明要找节点不在这棵子树中，所以当前根节点返回空。
  • 左右子树中有一个为空，另一个不为空。此时，有两种情况：
    • 两个节点都在不为空的那一棵子树中，先找到的节点直接返回，自然其就是公共祖先。
    • 不为空的那一棵子树中，只有其中一个节点，那么根节点将该节点反馈上去，给更高级的根节点进行判断。
  • 左右子树都不为空，那么说明两个节点分列当前节点两侧，即当前节点就为公共祖先。回溯到根节点时，根节点也只有一个子树有返回结果，自然输出该结果就是之前找到的公共祖先。

    代码

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    8. * };
    9. */
    10. class Solution {
    11. public:
    12.   TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    13.       if (root == NULL || root == p || root == q) return root;
    14.       TreeNode *lf_node = lowestCommonAncestor(root->left, p, q);
    15.       TreeNode *rg_node = lowestCommonAncestor(root->right, p, q);    
    16.       //根据当前节点左右子树的四种查找情况，来判断返回结果。
    17.       if (lf_node == NULL && rg_node == NULL) return NULL;
    18.       if (lf_node == NULL) return rg_node;
    19.       if (rg_node == NULL) return lf_node;
    20.       else return root;
    21.   }
    22. };