# 120191114 Recursive

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

preorder = [3,9,21,20,15,7]
inorder = [21,9,3,15,20,7]
Return the following binary tree:
pre root1 = 3
pre root2 = 9 [21,9]
pre root3 = 20 [15,20,7]

    3
   / \
  9  20
 /   / \
21  15  7

 public TreeNode buildTree(int[] preorder, int[] inorder) {
 
        TreeNode root = new TreeNode(preorder[0]);
        
        Stack<Int> leftStack = new Stack();
        Stack<Int> rightStack = new Stack();
        
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
               root.left = inorder[i - 1];
               root.right = inorder[i + 1];
            }
        }
 }

 public TreeNode buildTree(int[] preorder, int[] inorder) {
     TreeNode root = new TreeNode(preorder[0]);
     
}

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.

public int maxDepth(TreeNode root) { 3
    if (root == null) return 0;

    int left = maxDepth(root.left); 1
    int right = maxDepth(root.right); 2
       
    return Math.Max(left, right) + 1;
}

We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).

bunnyEars(0) → 0
bunnyEars(1) → 2
bunnyEars(2) → 4
.
.
.
bunnyEars(99) → bunnyEars(98) + 2
bunnyEars(100) → bunnyEars(99) + 2
(x)return input * 2;

      3
     / \
    2   1
   / \
  1   1

public int bunnyEars(int bunnies) {
  if (bunnies == 0) return 0;
  
  return bunnyEars(bunnies - 1) + 2;
}

Given n of 1 or more, return the factorial of n, which is n * (n-1) * (n-2) ... 1. Compute the result recursively (without loops).

factorial(1) → 1
factorial(2) → 2
factorial(3) → 6
.
.
.
factorial(9) → factorial(8) * 9
factorial(10) → factorial(9) * 10

public int factorial(int n) {
  if (n == 1) return 1;
  return factorial(n - 1) * n;
}

The fibonacci sequence is a famous bit of mathematics, and it happens to have a recursive definition. The first two values in the sequence are 0 and 1 (essentially 2 base cases). Each subsequent value is the sum of the previous two values, so the whole sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on. Define a recursive fibonacci(n) method that returns the nth fibonacci number, with n=0 representing the start of the sequence.

fibonacci(0) → 0
fibonacci(1) → 1
fibonacci(2) → 1
fibonacci(3) → fibonacci(2) + fibonacci(1)
fibonacci(4) → fibonacci(3) + fibonacci(2)

public int fibonacci(int n) {
  if (n == 0) return 0;
  if (n == 1 || n == 2) return 1;
  
  return fibonacci(n - 1) + fibonacci(n - 2);
}