# FB Week 1

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2      3
 \    
  5   

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
 
 helper method(node, path, list)
 if (left == null && right == null) list.add(path)
 if (left != null) helper(left, path + node.value "->", list);
 if (right != null) helper(right, path + node.value "->", list);
 
 
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList();
        if (root == null) return result;
        helper(root, "", result);
        return result;
 }
 
     public void helper(TreeNode node, String path, List<String> result) {
         if (node.right == null && node.left == null) {
             result.add(path + node.val);
         }
         if (node.left != null) {
             helper(node.left, path + node.val + "->", result);
         } 
          if (node.right != null) {
             helper(node.right, path + node.val + "->", result);
         } 
     }
}

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
      1
    /  \
   2    3
 /  \
4   5
 
Output: [4, 2, 5, 1, 3]

4 -> 2 -> 5 -> 1 -> 3

stack: 1, 2,

4

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList();
    if (root == null) return result;
    Stack<TreeNode> stack = new Stack();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()) {
        while(cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        result.add(cur.val);
        cur = cur.right;
    }
    return result;
}

      1
    /  \
   2    3
 /  \
4   5
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfs(root, result);
    return result;
}

public void dfs(TreeNode node, List<Interger> result) {
    if (node == null) return;
    dfs(node.left, result);
    result.add(node.val);
    dfs(node.right, result);
}

    5
   / \
  1   4
     / \
    3   6 (Not a BST)
Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

public boolean isValidBST(TreeNode root) {
    if (root == null) return false;
    
    Stack<TreeNode> stack = new Stack();
    stack.push(root);
    while(!stack.isEmpty()) {
       TreeNode current = stack.pop();
       if ((current.left != null && current.val < current.left.val) || (current.right != null && current.val > current.right.val)) {
           return false;
       } 
       
       if (current.left != null) {
           stack.push(current.left);
       }
       
       if (current.right != null) {
           stack.push(current.right);
       } 
    }
    
    return true;
}

public boolean isValidBST(TreeNode root) {
        if (root == null)  return true;
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null && pre.val >= root.val)
                return false;
            pre = root;
            root = root.right;
        }
        
        return true;
    }

[10,5,15,null,null,6,20]

10
/ \
5 15
/ \
13 20

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

     4
    / \
   2   5
  / \
 1   3

prev
dummy <-> 1 <-> 2 <-> 3 <-> 4 <-> 5

class Solution {    
    private Node prev = null; 
    
    public Node treeToDoublyList(Node root) {
          if (root == null) return root;
          Node dummy = new Dummy(0, null, null);
          prev = dummy;
          helper(root);
          // connect head and tail
          prev.left = dummy.right;
          dummy.right.left = prev;
          return dummy.right;
    }
    
    public void helper(Node node) {
        if (node == null) return;
        helper(node.left);
        node.left = prev;
        prev.right = node;
        prev = node;
        helper(node.right);
    }
}

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6
The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

    1
   / \
  2   5
 / \   \
3   4   6

private TreeNode prev = null;
public void flatten(TreeNode root) {
    if (root == null) reutn;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}

// Math.max(left, right) + node.val;
                1
               /
              2
             /
            3
           / 
          4  
         / \
        5  6
class Solution {
    private int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    public int helper(TreeNode node) {
        if (node == null) return 0;
        
        int left = Math.max(0, helper(node.left)); // 
        int right = Math.max(0, helper(node.right));
        
        max = Math.max(max, left + right + node.val); // 15
        
        return Math.max(left, right) + node.val; 13
    }
}

You may serialize the following tree:

     1 
   /  \
  2    3
      / \
      4  5 

as "[1,2,3,null,null,4,5]"

public class Codec {


    private static final String COMMA = ",";
    private static final String NULL = "null";
    
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return NULL;
        
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            sb.append(node.val).append(COMMA);
            if (node.left != null) {
                queue.offer(node.left);
            } else {
                sb.append(NULL).append(COMMA);
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                sb.append(NULL).append(COMMA);
            }
        }
        
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
       if (NULL.equals(data)) return null;
       String[] nodeString = data.splite(COMMA);
       Queue<String> queue = new LinkedList();
       for (String s: nodeString) {
           queue.offer(s);
       }
       return getNode(queue);
    }
    
    // as "[1,2,3,null,null,4,5]"

    // 1
     
    2  3
    
    private TreeNode getNode(Queue<String> queue) {
        if (queue.isEmpty()) return null;
        String nodeString = queue.poll();
        if (nodeString.equals(NULL)) {
            return null;
        } 

        TreeNode root = new TreeNode(Integer.parseInt(nodeString));
        root.left = getNode(queue); 
        root.right = getNode(queue); 
        return root;
    }
}

    public static final String NULL_STRING = "null";
    public static final String COMMA = ",";
    
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return NULL_STRING + COMMA;
        
        String left = serialize(root.left);
        String right = serialize(root.right);
        
        return root.val + COMMA + left + right;
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>();
        queue.addAll(Arrays.asList(data.split(",")));
        return deserializeHelper(queue);
    }
    
    public TreeNode deserializeHelper(Queue<String> queue) {
        String value = queue.poll();
        
        if (value.equals(NULL_STRING)) return null;
        
        TreeNode node = new TreeNode(Integer.valueOf(value));
        node.left = deserializeHelper(queue);
        node.right = deserializeHelper(queue);
        
        return node;
    }