二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

爱写bug

发布于 2020-03-12 18:48:35

8030

发布于 2020-03-12 18:48:35

文章被收录于专栏：爱写Bug爱写Bug

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

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

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

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

img

示例 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 为不同节点且均存在于给定的二叉树中。

Note:

All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.

解题思路：

只要熟悉树的遍历，应该都可以迅速完成该题。

关键点：

如果在 node 的左子树没找到与 p，q 相等的结点，递归函数返回null，公共祖先在右侧结点
如果在 node 的右子树没找到与 p，q 相等的结点，递归函数返回null，公共祖先在左侧结点
如果在 node 左右子树都找到与 p，q 相等的结点，递归函数返回公众祖先 node 结点

下面展示广度优先搜索的递归解法。

Java：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 基线条件
        if (root == null || root == p || root == q)
            return root;
        // 最小公共结点在左子树或右子树的情况
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        // 左子树或右子树未找到与 p，q 相等的结点时最小公共祖先在另一侧
        if (leftNode == null)
            return rightNode;
        if (rightNode == null)
            return leftNode;

        return root;
    }
}

Python：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root.val == p.val or root.val == q.val:
            return root
        left_node = self.lowestCommonAncestor(root.left, p, q)
        right_node = self.lowestCommonAncestor(root.right, p, q)

        if not left_node:
            return right_node
        if not right_node:
            return left_node

        return root

Golang：

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root.Val == p.Val || root.Val == q.Val {
        return root
    }
    leftNode := lowestCommonAncestor(root.Left, p, q)
    rightNode := lowestCommonAncestor(root.Right, p, q)

    if leftNode == nil {
        return rightNode
    }
    if rightNode == nil {
        return leftNode
    }
    return root
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-03-02，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js