LCA topic

Description

LCA of two nodes of binary tree

• Step 1: what is LCA ?

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

• Step 2： by applying divide and conquer thought,

  • at each node
  • we are determine if current node is the lca of w and v ?
    • if v and w is not null, and current node is lowest level, current node is lca
    • if we found a v in subtree, w is not found, we determine if current node is w, if it is w, and w is LCA
    • if we found a w in subtree, v is not found, we determine if current node is v, if its v, and v is LCA.
    • if nothing found, //will not happen in this case.

• Step 3: we utilize bottom-up method, since we need to find lowest level.

  • need to know, whether v or w has been found in left / right subtree.
  • first time
    • fromLeft != null && fromRight != null, lca = root;
    • fromleft == w || fromRight == v, and root == w / v, lca = root;

    //psb candidate lca of w and v at tree
    //how to guarantee this lca is the lowest one?
    public TreeNode LCA(TreeNode root, TreeNode w, TreeNode v) {
        if (root == null) {
            return root;
        } else if (root == w || root == v) {
            return root;
        }
        //root is not w or v
        TreeNode fromLeft = LCA(root.left, w, v);
        TreeNode fromRight = LCA(root.right, w, v);
        //there is only one chance that fromLeft != null && fromRight != null
        if (fromLeft != null && fromRight != null) {
            return root;
        } 
        //this covers the case we already found an LCA.
        return fromLeft == null ? fromRight : fromLeft;
    }
  

  LCA of two nodes of general tree

  • case 1 ：　

    among all children, find two non-null return, return root;

  • case 2 :

    among all children, find 1 non-null, return that node.

  • case 3: left == right == null, return null

LCA of Binary Search Tree

     //trick : 先排序w v (w < v)
     public TreeNode LCA(TreeNode root, TreeNode w, TreeNode v) {
         if (root == null) {
             return null;
         }
         if (root == w || root == v) {
             return root;
         }
         TreeNode l = null , r = null;
         if (v.val < root.val) {
             l = LCA(root.left, w, v);
         } else if (w.val > root.val) {
             l = LCA(root.right,w, v);
         } else {
             l = LCA(root.left, w, v);
             r = LCA(root.right,w, v);
         }
         if (l != null && r != null) {
             return root;
         } 
         return l == null ? r : l;
     }

Two nodes distance (LCA variant).

return value: <# found, distance>

• case 1
  • root == n1 || root == n2 -> return [1,0]
• case 2
  • left[1,h1] + right[1,h2] -> return [2,h1 + h2];
• case 3
  • left [0,h1] + right[1,h2] -> return [1,h2 + 1];
• case 4
  • left[1,h1] + right[0,h2] -> return [1,h1 + 1];
• case 5
  • left[0,h1] + right[0,h2] -> return [0,0]

Given a binary tree and two nodes, print out path.

    //this is not a good way to use bottom-up, just to demonstrate the idea of using return value
    public List<Integer> findPath(TreeNode root, TreeNode a, TreeNode b) {
        if (root == null) {
          return root;
        }
        if (root == a || root == b) {
          return new ArrayList<Integer>(Arrays.asList(root.val));
        }
        List<Integer> lRes = findPath(root.left,a,b);
        List<Integer> rRes = findPath(root.right,a,b);
        List<Integer> res = new ArrayList<Integer>();
        if (lRes != null && rRes != null) {
            res.addAll(lRes);
            res.add(root.val);
            res.addAll(rRes);
            return res;
        } else if (lRes != null) {
            lRes.add(root.val);
        } else if (rRes != null) {
            rRes.add(root.val);
        }
        return lRes == null ? rRes : lRes;
    }

A better idea is :

• find root to A path, root to B path.

• merge two linkedlist until met a common node.

  find deepest LCA of all leaf nodes.

• Step 1: clarify

  a) Definition of LCA : a node which has >= 2 leaf descendants b) Deepest : height minimum.

              7 
         /    |      \
        4     6       10
       / \            / \
      1   5          9  13
         / \        /     \ 
        3   6      8      18
       /   / \
      2   12 11