【MEDIUM】Lowest Common Ancestor of a Binary Tree

发布于: 2018-12-11 13:33
阅读: 56
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

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

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).”

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

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

分析过程

  • 输入:一棵二叉树和两个节点 p、q
  • 输出:最小公共节点
  • 思路:遍历树,看左右子树能否找到 p 和 q。如果当前节点不是 p 也不是 q,有三种情况:1、p 和 q 都位于左子树,那么遍历左子树时候会返回 p 或 q,而右子树会返回空。2、p 和 q 都在右子树,同上。3、p 和 q 分别在左子树和右子树,则当前节点就是最小公共节点。

解决方法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 到底了
        if (!root) {
            return nullptr;
        }
        // 如果是 a 和 b 的其中一个,直接返回当前节点
        if (root == p || root == q) {
            return root;
        }
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        
        if (left != nullptr && right != nullptr) {
            // 如果左右都不是空,则说明 a 和 b 分别在左右子树
            return root;
        } else {
            // 其中有一个不是空,另一个是空,则说明 a 和 b 都在不为空的那一边
            return (left != nullptr) ? left : right;
        }
    }
};

Swift 解法(此题在 LeetCode 中不支持该语言):

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

// 构造和题目中一致的树
var nodes = Array<TreeNode>.init()

for i in 0...9 {
    nodes.append(TreeNode.init(i))
}

let root = nodes[3]

root.left = nodes[5]
nodes[5].left = nodes[6]
nodes[5].right = nodes[2]
nodes[2].left = nodes[7]
nodes[2].right = nodes[4]

root.right = nodes[1]
nodes[1].left = nodes[0]
nodes[1].right = nodes[8]

func lowestCommonAncestor(_ root: TreeNode?, a: TreeNode, b: TreeNode) -> TreeNode? {
    // 到底了
    guard let root = root else {
        return nil
    }
    // 如果是 a 和 b 的其中一个,直接返回当前节点
    if root === a || root === b {
        return root
    }
    let left = lowestCommonAncestor(root.left, a: a, b: b)
    let right = lowestCommonAncestor(root.right, a: a, b: b)
    // 如果左右都不是空,则说明 a 和 b 分别在左右子树
    if left != nil && right != nil {
        return root
    } else {
        // 其中有一个不是空,另一个是空,则说明 a 和 b 都在不为空的那一边
        return (left != nil) ? left : right
    }
}

print(lowestCommonAncestor(root, a: nodes[2], b: nodes[4])?.val ?? "nil")
print(lowestCommonAncestor(root, a: nodes[5], b: nodes[8])?.val ?? "nil")

Thanks for reading.

All the best wishes for you! 💕