LeetCode 235. Lowest Common Ancestor of a Binary Search

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

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

翻譯

給一個二元搜尋樹(BST),再給兩個樹中的節點Node,找出這兩個Node的最低共同祖先節點,根據LCA在維基百科的定義: "最低共同祖先節點,是指在一個Tree T中的Node v, Node w存在一個最低層級共同的祖先T,同時 v與w也可以算是自己的祖先節點"

範例:以上面的樹來看,[2,8]的最低共同祖先節點為6。
[2,4]的最低共同祖先節點為2,因為2也算是自己的祖先節點

思路

一個BST,若任意節點的左子樹不為空,則左子樹所有節點的值都會比根節點小,從上面的樹可以看到6的左子樹裡面的節點為[2,0,4,3,5]均比6小。

  1. 取得根節點root的值,如果值落在目標節點[p,q]之間,代表root就是最低共同祖先節點
  2. 如果root比[p,q]都還小,用root.right取代root繼續往下找
  3. 如果root比[p,q]都還小,用root.left取代root繼續往下找

解題

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    var count = 0;

    while(true){
        var value =  root.val;

        if(p.val >= value && value >= q.val || p.val <= value && value <= q.val){
            return root;
        } else if(p.val > value && q.val > value){
            root =  root.right;
        } else {
            root =  root.left;
        }
    }
};

results matching ""

    No results matching ""