【EASY】Lowest Common Ancestor of a Binary Search Tree

发布于: 2018-12-11 12:47
阅读: 84
评论: 0
喜欢: 0

问题

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

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

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

        _______6______
       /              \
    __2__            __8__
   /     \         /       \
  0      _4_      7         9
        /   \
       3     5

Example 1:

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

Example 2:

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

Note:

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

分析过程

  • 输入:一棵二叉搜索树和两个节点,a 和 b
  • 输出:这两个节点的最小公共节点
  • 思路:遍历树,如果 a 和 b 都比当前节点小,那么肯定在左子树;都比当前大,那么肯定在右子树;如果 a 和 b 一个比当前节点大,一个比当前节点小,那么当前节点就是最小公共节点。如果 a 和 b 其中有一个和当前相等,那么这个点就是最小公共节点。

解决方法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 到底了
        if (!root) {
            return nullptr;
        }
        // 当前节点和 a 或者 b 相等的时候
        if (root == p || root == q) {
            return root;
        }
        // 当前节点在 a 和 b 之间的时候
        if (((root->val > p->val) && (root->val < q->val)) || ((root->val > q->val && root->val < p->val))) {
            return root;
        }
        // 当前节点比 a 和 b 都大的时候
        if ((root->val > p->val) && (root->val > q->val)) {
            return lowestCommonAncestor(root->left, p, q);
        }
        // 当前节点比 a he b 都小的时候
        if ((root->val < p->val) && (root->val < q->val)) {
            return lowestCommonAncestor(root->right, p, q);
        }
        // 理论上不会走到这里
        assert(0);
    }
};

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[6]

root.left = nodes[2]
nodes[2].left = nodes[0]
nodes[2].right = nodes[4]
nodes[4].left = nodes[3]
nodes[4].right = nodes[5]

root.right = nodes[8]
nodes[8].left = nodes[7]
nodes[8].right = nodes[9]

func lowestCommonAncestor(_ root: TreeNode?, a: Int, b: Int) -> TreeNode? {
    // 到底了
    guard let root = root else {
        return nil
    }
    // 当前节点和 a 或者 b 相等的时候
    if root === a || root === b {
        return root
    }
    // 当前节点在 a 和 b 之间的时候
    if (root.val > a.val && root.val < b.val) || (root.val > b.val && root.val < a.val) {
        return root
    }
    // 当前节点比 a 和 b 都大的时候
    if root.val > a.val && root.val > b.val {
        return lowestCommonAncestor(root.left, a: a, b: b)
    }
    // 当前节点比 a he b 都小的时候
    if root.val < a.val && root.val < b.val {
        return lowestCommonAncestor(root.right, a: a, b: b)
    }
    // 理论上不会走到这里,可以选择断言或者 fatalError
    return nil
}

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

Thanks for reading.

All the best wishes for you! 💕