LEETCODE 236. Lowest Common Ancestor of a Binary Tree 解题思路分析

题目大意:

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉树中。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=236

解题思路:

本题我用了2种解题方法,执行时间仅相差1ms,第一种略优于第二种,且代码量少,不过有些难于理解。而第二种虽然代码量多,但是思路非常简单,便于记忆。

先来看第一种递归思路。我们知道,如果节点p和q分别位于某个节点的左右两颗子树中,那么该节点就是返回结果。因此我们的主要目标就是从root开始查看p和q是否分别位于其左右两侧,如果不是,说明他们同时存在于root的某一侧之中,然后再以这一侧作为root,继续执行同样的逻辑。

那么如何判断p和q的位置?这里就需要用到递归,递归的根本目的是在子树中深度寻找p和q,看其是否在该子树中。递归开始,root逐层向下,当root等于p或者q时,说明找到了其中之一,开始向递归上层返回,并在上层的另一侧寻找另一个目标,如果找到,当前节点即是返回结果,如果没有则继续向上返回,直到找到为止。如果还没看懂,可以参考一下代码,代码中有详细注释。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // root若为空,还找个毛线,直接返回空(返回空的root本身即可)
    // root若等于p或者q,说明找到了其中一个元素,返回递归上一层。(*1)
    if (root == null || root == p || root == q) {
        return root;
    }
    // 如果当前层还没找到p或者q(root不等于p或者q),继续向下层寻找
    // 这里递归的顺序是先左侧深度遍历,再右侧。
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 如果左右两侧分别不为空,说明当前root下,p和q分别位于其左右,root即返回结果。(*2)
    // 这里解释下为什么是null判断,因为我们所有递归返回的结果要么空,要么是p或q
    // 因此,只要不是空,那么必定是p和q其中之一,为了便于理解,也可写成:
    // if (left == p && right == q || left == q && right == p)
    if (left != null && right != null) {
        return root;
    }
    // 如果左右两边都为空,那么不论返回左还是右,返回的都是空。
    // 如果左右两边其中之一不为空,那么返回那个不为空的值,这个不为空的值有2种可能
    // 其一是找到的p或者q,上面代码标注(*1)的返回值(与现在比更深层的递归返回值)。
    // 其二是找到的q或者q的共同父节点。上面代码标注(*2)的返回值(与现在比更深层的递归返回值)。
    // 第二种可能是找到了最终结果,所以当递归向上层返回时,可以保证左右两侧只有一个不为空
    // 因此,结果可以保证返回到最上层。
    return left == null ? right : left;
}

本解法用时5ms。


如果看了上面的分析和代码还是没搞懂,那么我们来看下一个非常简单的思路。这道题是要找任意两个节点的共同父节点,我们可以想一下,二叉树中每个节点有两个子节点,但父节点只有一个,也就是说,从p和q向二叉树上方走,他们分别只有一条路径能到达顶部root,所以在他们向上的2条路径发生相交时的节点即是结果。写代码时,我们可以从p和q出发,将他们每一个父节点记录到一个List中,当父节点第二次出现时,说明此时两条路径相交,该节点即是返回结果。这样做是不是很简单?!

但是问题来了,题目给出的TreeNode类中,并没有父节点信息,因此,我们需要做一步反向建模,将每个节点的父节点先找到,找到之后问题就会迎刃而解。思路比较清晰,我们直接看代码,代码中也有详细注释。

// 为了得到每个节点的父节点,我们自己定义一个类。
public class MyTreeNode {
    MyTreeNode(TreeNode node, MyTreeNode topNode) {
        treeNode = node;
        top = topNode;
    }
    MyTreeNode top; // 记录父节点
    TreeNode treeNode; // 记录当前节点
}

int valP, valQ; // 分别记录p和q的值

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
    valP = p.val;
    valQ = q.val;
    // 将root包装一下,记录下每个子节点的父节点。
    helper(root, null);
    // 定义一个用于保存p和q所以父节点用的List
    List<Integer> list = new ArrayList<>();
    // 因为p和q本身也可以作为父节点,先将其值存入list中。
    list.add(valP);
    list.add(valQ);
    // 开始遍历p和q的所有父节点。
    while (mp.top != null || mq.top != null) {
        if (mp.top != null) {
            // 如果list中已存在当前p的父节点,那么该父节点即是返回值
            if (list.contains(mp.top.treeNode.val)) {
                return mp.top.treeNode;
            }
            // 若list中不存在,将此父节点值存入list
            list.add(mp.top.treeNode.val);
            // 将p节点设为其父节点,为了下一次遍历
            mp = mp.top;
        }
        if (mq.top != null) {
            // 同理,如果list中已存在当前q的父节点,那么该父节点即是返回值
            if (list.contains(mq.top.treeNode.val)) {
                return mq.top.treeNode;
            }
            list.add(mq.top.treeNode.val);
            mq = mq.top;
        }
    }
    return null;
}

MyTreeNode mp, mq; // 记录包装好的p和q节点

// 该方法用于为每个节点记录其父节点
// 因为是找p和q的父节点,因此p和q以下的节点都不需要包装了
private void helper(TreeNode current, MyTreeNode root) {
    // 如果当前节点为空或者p和q均已包装好,可以结束此方法
    if (current == null || mp != null && mq != null) {
        return;
    }
    // 新建一个包装类MyTreeNode 
    MyTreeNode myTreeNode = new MyTreeNode(current, root);
    // 如果当前节点为p,则将包装好的p保存到全局变量中
    if (current.val == valP) {
        mp = myTreeNode;
    }
    // 如果当前节点为q,则将包装好的p保存到全局变量中
    if (current.val == valQ) {
        mq = myTreeNode;
    }
    // 继续为该节点的左右子节点包装,左右子节点的父节点为当前节点。
    helper(current.left, myTreeNode);
    helper(current.right, myTreeNode);
}

本解法用时6ms,略微逊色于第一种解法。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/236-lowest-common-ancestor-of-a-binary-tree-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。