# 20191117 Pre, In, Post Order Recursive

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /  \
      2     6
     / \    
    1   3  
    
while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

// TIME: NLOG(N)

List<Integer> list;
public int minDiffInBST(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    list = new ArrayList<>();
    DFS(root);
    
    Collections.sort(list);
    
    int result = Integer.MAX_VALUE;
    for (int i = 1; i < list.size(); i++) {
        result = Math.min(result, list.get(i) - list.get(i - 1));
    }
    
    return result;
}

// Preorder traverse
public void DFS(TreeNode node) {
    if (node == null) {
        return;
    }
    list.add(node.val);
    DFS(node.left);
    DFS(node.right);
}

4
/ \
2 6
/ \
1 3

class Solution {
    Integer prev, ans; 
    public int minDiffInBST(TreeNode root) {
        prev = null;
        ans = Integer.MAX_VALUE;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left); 
        if (prev != null) {
          ans = Math.min(ans, node.val - prev);
        }
        prev = node.val;
        dfs(node.right);
    }
}

Pre, In, Post Order

class Solution {
    List<Integer> result;
    public List<Integer> dfsOrder(TreeNode root) {
        result = new ArrayList<>();
        dfs(root);
        return result;
    }
    
    public void dfs(TreeNode node) {
        if (node == null) return;
        
        dfs(node.left);
        dfs(node.right);
    }
}

odd 奇數
even 偶數
We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).

bunnyEars2(0) → 0
bunnyEars2(1) → 2 bunnyEars2(0) + 2
bunnyEars2(2) → 5 bunnyEars2(1) + 3
bunnyEars2(3) → 7 // 2 + 3 + 2 = 7
bunnyEars2(n) →

public int bunnyEars2(int bunnies) {
    if (bunnies == 0) return 0;
    if (bunnies % 2 == 0) {
       return bunnyEars2(bunnies - 1) + 3;
    } else {
       return bunnyEars2(bunnies - 1) + 2;
    }
}

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

triangle(0) → 0
triangle(1) → 1
triangle(2) → 3
triangle(3) → 6
triangle(4) → 10
O
O O
O O O
O O O O

// f(n - 1) + n

public int triangle(int rows) {
  if (rows == 0) return 0;
  return triangle(rows - 1) + rows; 
}

Given a non-negative int n, return the sum of its digits recursively (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).

sumDigits(126) → 9
sumDigits(49) → 13
sumDigits(12) → 3
sumDigits(12345) → 15
sumDigits(1) → 1

// 12345 → sumDigits(1234) + 5
// 1234 → sumDigits(123) + 4
// 123 → sumDigits(12) + 3

public int sumDigits(int n) {
   if (n == 0) return 0;
   if (n == 1) return 1;
   return sumDigits(n / 10) + n % 10;
}

Given a non-negative int n, return the count of the occurrences of 7 as a digit, so for example 717 yields 2. (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).

count7(717) → 2
count7(7) → 1
count7(123) → 0
count7(77777) → 5
count7(77777) → n % 10 == 7 ? count7(7777) + 1 : count7(7777)
count7(7777) →
count7(777) →

public int count7(int n) {
  if (n == 0) return 0;
  if (n % 10 == 7) {
     return count7(n / 10) + 1;
  } else {
     return count7(n / 10);
  }
}

https://codingbat.com/java/Recursion-1

Given a complete binary tree, count the number of nodes.

Note:

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.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

List<Integer> list;

public int countNodes(TreeNode root) {
    if(root == null) return 0;
    list = new ArrayList<>();
    dfs(root);
    
    return list.size();
}

public void dfs(TreeNode node) {
    if (node == null) return;
    
    list.add(node.val);
    dfs(node.left);
    dfs(node.right);
}

countNodes(n) 5
/ \
countNodes(n.left)=3 countNodes(n.right)=1
/ \
countNodes(n.left.left)=1 countNodes(n.left.right)=1
/\
0 0

class Solution {
  public int countNodes(TreeNode root) {
    return root != null ? 1 + countNodes(root.right) + countNodes(root.left) : 0;
  }
}

class Solution {
  // Return tree depth in O(d) time.
  public int computeDepth(TreeNode node) {
    int d = 0;
    while (node.left != null) {
      node = node.left;
      ++d;
    }
    return d;
  }

  // Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
  // Return True if last level node idx exists. 
  // Binary search with O(d) complexity.
  public boolean exists(int idx, int d, TreeNode node) {
    int left = 0, right = (int)Math.pow(2, d) - 1;
    int pivot;
    for(int i = 0; i < d; ++i) {
      pivot = left + (right - left) / 2;
      if (idx <= pivot) {
        node = node.left;
        right = pivot;
      }
      else {
        node = node.right;
        left = pivot + 1;
      }
    }
    return node != null;
  }

  public int countNodes(TreeNode root) {
    // if the tree is empty
    if (root == null) return 0;

    int d = computeDepth(root);
    // if the tree contains 1 node
    if (d == 0) return 1;

    // Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
    // Perform binary search to check how many nodes exist.
    int left = 1, right = (int)Math.pow(2, d) - 1;
    int pivot;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (exists(pivot, d, root)) left = pivot + 1;
      else right = pivot - 1;
    }

    // The tree contains 2**d - 1 nodes on the first (d - 1) levels
    // and left nodes on the last level.
    return (int)Math.pow(2, d) - 1 + left;
  }
}

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

    3
   / \
  9  20
    /  \
   15   7
         \
          4
          \
          10
return its depth = 5.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;  
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) retunr 0;
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree
          1
         / \
        2   3
       / \     
      4   5    
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

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.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

public List<Integer> rightSideView(TreeNode root) {
   List<Integer> list = new ArrayList();
   if (root == null) return list;
   Stack<TreeNode> stack = new Stack();
   Map<Integer, Integer> map = HashMap();
   stack.push(root);
   int depth = 0
   while(!stack.isEmpty()) {
     TreeNode curr = stack.pop();
     map.put(depth, curr.val);
     depth++;
     if (curr.left != null) {
         stack.push(curr.left);
     }
     if (curr.right != null) {
         stack.push(curr.right);
     }
   }
   
   for (int i : map.values()) {
      list.add(i);
   }     
   return list;
}

public List<Integer> rightSideView(TreeNode root) {
    if (root == null) return new ArrayList<>(); 
    List<Integer> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            
            if (i == 0) {
                result.add(node.val);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
        }
    }
    
    return result;
}

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

 public List<List<Integer>> levelOrder(TreeNode root) {
        
}