Binary Tree

前序遍历：根 - 左 - 右
preorder: root - left - right

144. Binary Tree Preorder Traversal

注意：判断root是否为空

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

    //stack
    public List<Integer> preorderTraversal2(TreeNode root) {
        Stack<TreeNode> tree = new Stack<>();
        List<Integer> list = new ArrayList<Integer>();
        if(root!=null) tree.push(root);
        while(!tree.isEmpty()){
            root = tree.pop();
            list.add(root.val);
            if(root.right!=null) tree.push(root.right);
            if(root.left!=null) tree.push(root.left);
        }
        return list;
    }
}

中序遍历：左 - 根 - 右
inorder traversal: left - root - right

94. Binary Tree Inorder Traversal

class Solution {
    //recursive
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        recursive(root, list);
        return list;
    }
    public void recursive(TreeNode root, List<Integer> list){
        if(root!=null){
            recursive(root.left, list);
            list.add(root.val);
            recursive(root.right, list);
        }
    }
    //stack
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> tree = new Stack<>();
        while(root!=null || !tree.isEmpty()){
            while(root!=null){
                tree.push(root);
                root=root.left;
            }
            root=tree.pop();
            list.add(root.val);
            root=root.right;
        }
        return list;
    }
}

173. Binary Search Tree Iterator

public class BSTIterator {
    private TreeNode root;
    private TreeNode cur;
    private Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        this.root = root;
        this.cur = root;
        stack = new Stack<>();
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(root!=null || !stack.isEmpty()) {
            cur=root;
            while(cur!=null) {
                stack.push(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            root=cur.right;
            return true;
        }
        return false;
    }
    /** @return the next smallest number */
    public int next() {
        return cur.val;
    }
}

不知道hasNext()的时间复杂度是不是average O(1)。
还需要返工。
参考：https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

后序遍历：左 - 右 - 根 （从叶子结点开始遍历，便于求和）
postorder: left - right - root

145. Binary Tree Postorder Traversal

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

    //stack
    public List<Integer> postorderTraversal(TreeNode root) {
        //注意这里是linkedlist
        LinkedList<Integer> list = new LinkedList<>();
        if(root==null) return list;
        Stack<TreeNode> tree = new Stack<>();
        tree.push(root);
        while(!tree.isEmpty()){
            root=tree.pop();
            list.addFirst(root.val);
            if(root.left!=null) tree.push(root.left);
            if(root.right!=null) tree.push(root.right);
        }
        return list;
    }
}

563. Binary Tree Tilt

543. Diameter of Binary Tree

找每一个node下最长的path：左孩子最大深度+右孩子最大深度+2
找一个node的最大深度：max(左孩子最大深度，右孩子最大深度) + 1

class Solution {
    private int longest = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return longest;
    }
    public int maxDepth(TreeNode root) {
        if(root==null) return -1;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        longest = Math.max(left + right + 2, longest);
        return Math.max(left, right) + 1;
    }
}

687. Longest Univalue Path

124. Binary Tree Maximum Path Sum

几个陷阱：
path至少包含一个结点，相当于无向图，求任意两结点之间值的最大值。
如果返回根节点，每一层都只能右一个点。

class Solution {
    private int largest;
    public int maxPathSum(TreeNode root) {
        largest = root.val;
        largestPath(root);
        return largest;
    }
    //递归：必须经过根节点 / 只有一边的子节点被用到
    public int largestPath(TreeNode node) {
        if(node==null) return 0;
        //有三种选择：左+右+根，左+根，右+根
        //如果是负值，直接变为零
        int left = Math.max(0, largestPath(node.left));
        int right = Math.max(0, largestPath(node.right));
        largest = Math.max(left + right + node.val, largest);
        return Math.max(left, right) + node.val;
    }   
}

参考：https://www.youtube.com/watch?v=9ZNky1wqNUw&t=4s

root==null: depth=0;
only a root without left or right child: depth=1

105. Construct Binary Tree from Preorder and Inorder Traversal

preorder的start是当前根节点，inoder找到当前根节点之后，它左边都是左子树，右边都是右子树。让当前root的index是i。
root.left就找[instart, i-1]，root.right就找[i+1, end]
root.left的prestart就是prestart+1
root.right的prestart就是prestart+左边元素个数+1
左边元素个数是i-instart

//pre: 根 左 右
//in: 左 根 右
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper (0, 0, preorder.length-1, preorder, inorder);
    }
    public TreeNode helper (int preStart, int inStart, int end, int[] preorder, int[] inorder) {
        if(preStart>preorder.length-1 || inStart>end) return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int i=inStart;
        while(i<= end){
            if(inorder[i]==preorder[preStart]) break;
            i++;
        }
        root.left=helper (preStart+1, inStart, i-1, preorder, inorder);
        root.right=helper (preStart+i-inStart+1, i+1, end, preorder, inorder);
        return root;
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

同上一题

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(0, postorder.length-1, inorder.length-1, inorder, postorder);
    }
    public TreeNode helper(int in_str, int post_str, int in_end, int[] inorder, int[] postorder) {
        if(post_str<0 || in_end<in_str) return null;
        TreeNode root = new TreeNode(postorder[post_str]);
        int i = 0; // the posit of root
        while(inorder[i]!=postorder[post_str]) i++;
        root.right = helper(i+1, post_str-1, in_end, inorder, postorder);
        root.left = helper(in_str, post_str-in_end+i-1, i-1, inorder, postorder);
        return root;
    }
}

完全二叉树 Complete Binary Tree
只有最后一层可以不被填满，不被填满的空缺全都集中在右边
特点：如果全都被填满，node个数是2^h-1。

222. Count Complete Tree Nodes

思路： 求左子树深度和右子树深度之差，如果深度相同，说明node全满，直接用公式求node个数。
沿着左子树的左边求左子树深度，沿着右子树的左边求右子树深度，如果两边深度相同，说明左子树是满的，如果两边不同，说明右子树是满的。

位运算比pow()快很多

//time: O(logn*logn)  space: O(n)
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        if(left==right) return (1 << left) + countNodes(root.right);
        else return (1 << right) + countNodes(root.left);
    }
    public int depth(TreeNode root) {
        int depth=0;
        while(root!=null){
            root=root.left;
            depth++;
        }
        return depth;
    }
}

参考：https://www.jianshu.com/p/0dc42a7f36f0