Lowest Common Ancestor of a Binary Search Tree, Lowest Common Ancestor of a Binary Tree, Invert Binary Tree, Kth Smallest Element in a BST, Binary Tree Right Side View, Count Complete Tree Nodes

Posted on 2015-09-23   |   In 刷题   |  

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

1
2
3
4
5
6
7
     _______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.

Solution

  • As long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root’s), move down current node, walks straight from the root to the LCA
1
2
3
4
5
6
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while((p.val-root.val) * (q.val-root.val) > 0){
        root = p.val > root.val? root.right : root.left;
    }   
    return root;
}

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

1
2
3
4
5
6
7
     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4

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

Solution

1
2
3
4
5
6
7
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //if q/p found, return the node, if reached null, return null
    if(root==null || root==q || root==p) return root;
    TreeNode left= lowestCommonAncestor(root.left, p, q);
    TreeNode right= lowestCommonAncestor(root.right, p, q);
    return (left!=null && right!=null) ? root : (left!=null) ? left : right;
}

—

Invert Binary Tree

Invert a binary tree.

1
2
3
4
5
6
7
8
9
10
11
     4
   /   \
  2     7
 / \   / \
1   3 6   9
to
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

DFS Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode invertTree(TreeNode root) {
    if(root==null || (root.left==null && root.right==null)) return root;
    TreeNode tmp=root.left;
    root.left=root.right;
    root.right=tmp;
    if(root.left!=null){
        invertTree(root.left);
    }
    if(root.right!=null){
        invertTree(root.right);
    }
    return root;
}

Or more concisely

1
2
3
4
5
6
7
public TreeNode invertTree(TreeNode root) {
   if(root==null) return null;
   TreeNode tmpright=root.right;
   root.right=invertTree(root.left);
   root.left=invertTree(tmpright);
   return root;
}

BFS Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public TreeNode invertTree(TreeNode root) {
   if(root==null) return null;
   LinkedList<TreeNode> q=new LinkedList<TreeNode>();
   q.offer(root);
   while(!q.isEmpty()){
       TreeNode cur=q.poll();
       TreeNode tmp=cur.left;
       cur.left=cur.right;
       cur.right=tmp;
       if(cur.left!=null) q.offer(cur.left);
       if(cur.right!=null) q.offer(cur.right);
   }
   return root;
}

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Hint:
Try to utilize the property of a BST.
What if you could modify the BST node’s structure?
The optimal runtime complexity is O(height of BST).

O(n) Solution

  • Inorder walk, stop when we get to k elementsm, return the kth. 
1
2
3
4
5
6
7
8
9
10
11
12
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        inorder(root, k, list);
        return list.get(k-1);
    }
    private void inorder(TreeNode root, int k,  ArrayList<Integer> list){
    if(list.size()>=k) return;
    if(root==null) return;
    inorder(root.left, k, list);
    list.add(root.val);
    inorder(root.right, k, list);
}

Augmented Tree O(logn) Solution

  • Binary search on left subtree count k
  • If count == k+1 then current root is kth smallest
  • Otherwise keep looking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static class TreeNodeWithCount{
    int val;
    int count;
    TreeNodeWithCount left;
    TreeNodeWithCount right;
    TreeNodeWithCount(int x) {val = x; count = 1;};
  }
  
  private static TreeNodeWithCount buildtree(TreeNode root){
        if (root == null) return null;
        TreeNodeWithCount rootWithCount = new TreeNodeWithCount(root.val);
        rootWithCount.left = buildtree(root.left);
        rootWithCount.right = buildtree(root.right);
        if (rootWithCount.left != null) rootWithCount.count += rootWithCount.left.count;
        if (rootWithCount.right != null) rootWithCount.count += rootWithCount.right.count;
        return rootWithCount;
  }
  
  public static TreeNodeWithCount findkthsmallest(TreeNodeWithCount root, int k){
    int count=0;
    if(root.left!=null)  count=root.left.count;
    if(count>=k){
      return findkthsmallest(root.left, k);
    }
    else if(count<k-1){
      return findkthsmallest(root.right, k-count-1);
    }
    return root;
  }

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

1
2
3
4
5
6
7
8
For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
You should return [1, 3, 4].

Iterative Solution

  • Reverse BFS,add each layer’s first element to result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> rightSideView(TreeNode root) {
       List<Integer> res= new ArrayList<Integer>();
       if(root==null) return res;
       Queue<TreeNode> q = new LinkedList<TreeNode>();
       q.offer(root);
       while(!q.isEmpty()){
           int size = q.size();
           for(int i=0;i<size;i++){
               TreeNode cur = q.poll();
               if(i==0){
                   res.add(cur.val);
               }
               if(cur.right!=null){
                   q.offer(cur.right);
               }
               if(cur.left!=null){
                   q.offer(cur.left);
               }
           }
       }
       return res;
   }

Recursive Solution

  • Each depth of the tree only select one node.
  • View depth is current size of result list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res= new ArrayList<Integer>();
    if(root==null) return res;
    dfs(res, root, 0);
    return res;
}
private void dfs(List<Integer> res, TreeNode r, int level){
    if(r==null) return;
    if(level==res.size()) {
        res.add(r.val);
    }
    dfs(res, r.right, level+1);
    dfs(res, r.left, level+1);
}

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Solution

  • Use bit manipulation, faster than Math.pow()
  • Find the leftmost height and rightmost height, if equal just return the full nodes, if not continue to subtrees 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int left = getheight(root.left, "left");
    int right = getheight(root.right, "right");
    if(left==right) return (2<<left) - 1;
    return 1 + countNodes(root.left) + countNodes(root.right);
}
public int getheight(TreeNode root, String s){
    if(root==null) return 0;
    if(s.equals("left")){
        return 1 + getheight(root.left, "left");
    }
    else{
        return 1 + getheight(root.right, "right");
    }
}

```

#Tree #DFS #BFS
Palindrome Partitioning, Palindrome Partitioning II, Word Break, Word Break, Word Break II
Clone Graph, Populating Next Right Pointers in Each Node, Populating Next Right Pointers in Each Node II, Word Ladder, Word Ladder II