leetcode--tree

94. Binary Tree Inorder Traversal

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        helper(root, list);
        return list;
    }
    
    public void helper(TreeNode root, List<Integer> list) {
        if(root == null) {
            return;
        }
        helper(root.left, list);
        list.add(root.val);
        helper(root.right, list);
    }
}

144. Binary Tree Preorder Traversal

class Solution {
    // root left right
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        
        preorderTraversalHelper(root, result);
        
        return result;
    }
    
    private List<Integer> preorderTraversalHelper(TreeNode node, List<Integer> list) {
        if (node == null) {
            return list;
        }
        
        list.add(node.val);
        
        preorderTraversalHelper(node.left, list);
        preorderTraversalHelper(node.right, list);
        
        return list;
    }
}

230. Kth Smallest Element in a BST

class Solution {
    int value = Integer.MAX_VALUE;
    int idx = 0;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null)   return -1;
        findKthSmallest(root, k);
        if (idx == k)
            return value;
        
        return -1;
    }
    
    int findKthSmallest(TreeNode root, int k) {
        if (root.left != null) {
            int left = findKthSmallest(root.left, k);
            if (left == k)  return left;
        }
        
        idx++;
        if (idx == k) {
            value = root.val;
            return idx;
        }
        
        if (root.right != null)
            return findKthSmallest(root.right, k);
        else    return idx;
    }
}   

173. Binary Search Tree Iterator

public class BSTIterator {
    private TreeNode root;
    public BSTIterator(TreeNode root) {
        this.root = root;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return root != null;
    }

    /** @return the next smallest number */
    public int next() {
        if (root == null) {
            return -1;
        }
        
        int ans = 0;
        while (root != null) {
            if (root.left == null) {
                ans = root.val;
                root = root.right;
                break;
            } else {
                TreeNode tmp = root.left;
                while (tmp.right != null && tmp.right != root) {
                    tmp = tmp.right;
                }
                
                if (tmp.right == null) {
                    tmp.right = root;
                    root = root.left;
                } else {
                    ans = root.val;
                    tmp.right = null;
                    root = root.right;
                    break;
                }
            }
        }
        
        return ans;
    }
}  

102. Binary Tree Level Order Traversal

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
       /** List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        q.offer(null);
        while(!q.isEmpty() && q.peek()!= null){
            List<Integer> temp = new ArrayList<>();
            TreeNode p = q.poll();
            while(p != null){
                temp.add(p.val);
                if(p.left != null)
                    q.offer(p.left);
                if(p.right != null)
                    q.offer(p.right);
                p = q.poll();
            }
            res.add(temp);
            q.offer(null);
        }
        return res;*/
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        helper(res,root,0);
        return res;
    }
    
    private void helper(List<List<Integer>> res, TreeNode root, int level){
        if(root == null)
            return;
        if(level >= res.size())res.add(new ArrayList<Integer>());
        res.get(level).add(root.val);
        helper(res,root.left,level+1);
        helper(res,root.right,level+1);
    }
}

199. Binary Tree Right Side View

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        getRightView(root, 0, result);
        return result;
    }
    
    public void getRightView(TreeNode root, int currentDepth, List<Integer> result){
        if(root==null)
            return;
        if(currentDepth == result.size()){
            result.add(root.val);
        }
        getRightView(root.right, currentDepth + 1, result);
        getRightView(root.left, currentDepth + 1, result);
    }
}  

96. Unique Binary Search Trees

class Solution {
    public int numTrees(int n) {
        if(n <= 0) return 0;
        
        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < i; j++){
                res[i] += res[j] * res[i - j - 1];
            }
        }
        
        return res[n];
    }
}   

116. Populating Next Right Pointers in Each Node

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return ;
        
        if (root.left != null) {
            root.left.next = root.right;
        }
        if (root.right != null) {
            if (root.next != null) {
                root.right.next = root.next.left;
            }
            else { // root.next == null
                root.right.next = null;
            }
        }
        connect(root.left);
        connect(root.right);
    }
}

103. Binary Tree Zigzag Level Order Traversal

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res,root,1);
        return res;
    }
    public void helper(List<List<Integer>> res, TreeNode node,int lvl){
        if(node==null) return;
        if(lvl>res.size()){
            List<Integer> newlist = new ArrayList<>();
            newlist.add(node.val);
            res.add(newlist);
        }
        else{
            if(lvl%2==0) res.get(lvl-1).add(0,node.val);
            else res.get(lvl-1).add(node.val);
        }
        helper(res,node.left,lvl+1);
        helper(res,node.right,lvl+1);
    }
}

114. Flatten Binary Tree to Linked List

class Solution {
    private TreeNode last = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (last != null) {
            last.left = null;
            last.right = root;
        }
        last = root;
        
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
}

public class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        if(root.left != null){
            flatten(root.left);
            TreeNode cur = root;
            TreeNode temp = root.right;
            root.right = root.left;
            root.left = null;
            while(cur.right != null) cur = cur.right;
            cur.right = temp;
            flatten(temp);
        }
        else{
            flatten(root.right);
        }
    }
}

113. Path Sum II

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null) return res;
        List<Integer> temp = new ArrayList<>();        
        helper(root, sum, temp, res);
        return res;
        
    }
    
    private void helper(TreeNode root, int sum, List<Integer> temp, List<List<Integer>> res) {
        if(root == null) return;
        else if (root.val == sum && root.left == null && root.right == null) {
            temp.add(root.val);
            res.add(new ArrayList<>(temp));
            temp.remove(temp.size() - 1);
            return;
        }else 
            temp.add(root.val);
        helper(root.left, sum - root.val, temp, res);
        helper(root.right, sum - root.val, temp, res);  
        temp.remove(temp.size() - 1);
    }
}

105. Construct Binary Tree from Preorder and Inorder Traversal

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder,0,inorder,inorder.length-1,0);
        
    }
    private TreeNode buildTree(int[] preorder,int p,int[] inorder,int start,int end){
        if(start<end || p>preorder.length-1)
            return null;
        int val = preorder[p];
        int index = start;
        for(int i=start;i>=end;i--){
            if(val==inorder[i]){
                index = i;
                break;
            }
        }
        TreeNode node = new TreeNode(val);
        node.left = buildTree(preorder,p+1,inorder,index-1,end);
        node.right = buildTree(preorder,p+(index-end)+1,inorder,start,index+1);
        return node;
    }
}

117. Populating Next Right Pointers in Each Node II

public class Solution {
    public void connect(TreeLinkNode root) {
        while (root != null) {
            TreeLinkNode current = root;
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode p = dummy;
            
            while (current != null) {
                if (current.left != null) {
                    p.next = current.left;
                    p = p.next;
                }
                if (current.right != null) {
                    p.next = current.right;
                    p = p.next;
                }
                current = current.next;
            }
            
            root = dummy.next;
        }
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

class Solution {
    int p_inorder;
    int p_postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        p_inorder = inorder.length - 1;
        p_postorder = postorder.length-1;
        return helper(inorder, postorder, null);
    }
    public TreeNode helper(int[] inorder, int[] postorder, TreeNode end){
        if(p_postorder < 0){
            return null;
        }
        TreeNode root = new TreeNode(postorder[p_postorder--]);
        if(inorder[p_inorder] != root.val){
            root.right = helper(inorder,postorder,root);
        }
        p_inorder--;
        if((end == null) || (inorder[p_inorder] != end.val)){
            root.left = helper(inorder,postorder,end);
        }
        return root;
    }
}

236. Lowest Common Ancestor of a Binary Tree

class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    } 
    
    // BFS, map<curr, parent>, common ancestor must be p or q or one of their parent
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        Map<TreeNode, TreeNode> map = new HashMap<>();
        Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp.left != null) {
                map.put(tmp.left, tmp);
                queue.offer(tmp.left);
            }
            if (tmp.right != null) {
                map.put(tmp.right, tmp);
                queue.offer(tmp.right);
            }
        }
        Set<TreeNode> set = new HashSet<>();
        while (p != null) {
            set.add(p);
            p = map.get(p);
        }
        while (!set.contains(q)) {
            q = map.get(q);
        }
        return q;
    }
}  

222. Count Complete Tree Nodes

public class Solution {
    public int countNodes(TreeNode root) {
        
        if(root==null){
            return 0;
        }
        
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        int count=1;
        while(!q.isEmpty()){
            TreeNode temp = q.poll();
            if(temp.val!=-100){
                temp.val=-100;
                
                if(temp.left!=null){
                    q.offer(temp.left);
                    count++;
                }
                
                if(temp.right!=null){
                    q.offer(temp.right);
                    count++;
                }
            }
        }
        return count;
    }
}

98. Validate Binary Search Tree

class Solution {
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean helper(TreeNode root, long min, long max){
        if(root == null)
            return true;
        
        if(root.val >= max || root.val <= min)
            return false;
        
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }
}