Leetcode 236. Lowest Common Ancestor of a Binary Tree

xindoo

发布于 2021-01-21 18:02:01

5030

发布于 2021-01-21 18:02:01

题目链接 236. Lowest Common Ancestor of a Binary Tree

　　根据LCA的定义，二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点，LCA的定义没什么好解释的，主要是这道题的解法。　　我们要找p和q的最小公共节点，我开始想到的方法是先找出root分别到p和q的路径，既然路径都知道了，就从两条路径的末尾倒着往前来，第一个共同节点就是LCA，但其实有更简单易懂的方法。　　对于任意一个p和q的祖先节点node，都有三种情况，情况一：p和q的LCA在node的左子树，情况二：p和q的LCA在node的右子树，情况三：node就是p和q的LCA。　　说到递归，肯定是有边界条件的，这里的边界条件除了递归到叶子节点外，还有就是到达p或q，因为你p或者q的子孙节点不可能是p和q的LCA。在代码实现过程中，如果没到递归边界，我们先从左子树找LCA，比如找到了liftLCA。再从从右子树找LCA，比如找到了rightLCA。　　这里有几种情况：(1). liftLCA和rightLCA都不为空，肯定liftLCA和rightLCA分别是p和q，所以当然root节点肯定是LCA。(2).liftLCA和rightLCA其中之一为空，可能是在左子树或者又子树中找到了LCA，直接返回非空的一个。(3).liftLCA和rightLCA其中之一为空，还有可能是当前root节点的左右子树只包含p或q节点其中之一，这种情况递归回溯到上层是就会最终变成情况（1）或（2）。　　我的解题代码如下（Run Time：12ms）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (null == root) {
            return null;
        }
        if (root == p || root == q) {  //递归边界
            return root;
        }
        TreeNode liftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p,  q);
        if (null != liftLCA && null != rightLCA) { //情况（1）
            return root;  
        } 
        return liftLCA != null ? liftLCA : rightLCA; //情况（2）（3）
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除

数据分析