Lowest Common Ancestor of a Binary Tree leetcode

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p , q);
        if (left != null && right != null) {
            return root;
        } else if (right != null) {
            return right;
        } else if (left != null) {
            return left;
        } else {
            return null;
        }
    }
}

Binary Tree Right Side View leetcode

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.

For example:
Given the following binary tree,

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

You should return [1, 3, 4].

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

Binary Tree Upside Down leetcode

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1  

方法1: 类似reverse linkedlist, 从后往前一步一步的reverse

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode parent = null;
        TreeNode right = null;
        while (root != null) {
            TreeNode left = root.left;
            root.left = right;
            right = root.right;
            root.right = parent;
            parent = root;
            root = left;
        }
        return parent;
    }
}

方法2 用stack, 从前往后reverse

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Stack stack = new Stack();
        while (root.left != null) {
            stack.push(root);
            root = root.left;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (stack.isEmpty()) {
                node.left = null;
                node.right = null;
            } else {
                node.left = stack.peek().right;
                node.right = stack.peek();
            }
        }
        return root;
    }
}

Binary Tree Postorder Traversal leetcode

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

postorder： 左－右－中

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root == null){
            return result;
        }
        ArrayList<Integer> left = postorderTraversal(root.left);
        ArrayList<Integer> right = postorderTraversal(root.right);
        result.addAll(left);
        result.addAll(right);
        result.add(root.val);
        return result;
        
    }
}

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        helper(res, root);
        return res;
    }
    public void helper(List<Integer> res, TreeNode root) {
        if (root == null) {
            return;
        }
        helper(res, root.left);
        helper(res, root.right);
        res.add(root.val);
    }
}
public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode peak = stack.peek();
                if (peak.right != null && pre != peak.right) {///如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点）就访问右结点 /
                    root = peak.right;
                } else {////如果栈顶元素右结点是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕 需要把栈顶元素加入结果并且回溯上一层
                    stack.pop();
                    res.add(peak.val);
                    pre = peak;
                }
                
            }
        }
        return res;
    }
}

Convert Sorted List to Binary Search Tree leetcode

因为链表和array不同, 不能直接访问中间元素.

中序遍历，按照递归中序遍历的顺序对链表结点一个个进行访问，而我们要构造的二分查找树正是按照链表的顺序来的。

思路就是先对左子树进行递归，然后将当前结点作为根，迭代到下一个链表结点，最后在递归求出右子树即可。
因为listnode不能传递 所以要放入一个arraylist中

整体过程就是一次中序遍历，时间复杂度是O(n)，总的空间复杂度是栈空间O(logn)。

 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<ListNode> res = new ArrayList<ListNode>();
        res.add(head);
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            cur = cur.next;
            count++;//找出链表的总个数
        }
        return helper(res, 0, count - 1);
    }
    public TreeNode helper(ArrayList<ListNode> res, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (end + start) / 2;
        TreeNode left = helper(res, start, mid - 1);
        TreeNode root = new TreeNode(res.get(0).val);
        root.left = left;
        res.set(0, res.get(0).next);//指向链表的下一个元素 因为中序遍历 下一个要访问的点就是该点
        root.right = helper(res, mid + 1, end);
        return root;
    }
}

第二种做法是把list存在一个hashmap里面， 然后向做arry那样的递归做， 时间复杂O（n）， 空间O(n)

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    public TreeNode sortedListToBST(ListNode head) {  
        if (head == null) {
            return null;
        }
        HashMap map = new HashMap();
        int i = 0;
        while (head != null) {
            map.put(i, head);
            i++;
            head = head.next;
        }
        return helper(0, i - 1, map);
    }
    public TreeNode helper(int start, int end, HashMap map) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        ListNode node = map.get(mid);
        TreeNode head = new TreeNode(node.val);
        head.left = helper(start, mid - 1, map);
        head.right = helper(mid + 1, end, map);
        return head;
    }
}

Populating Next Right Pointers in Each Node leetcode

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

node的left child 要指向right child, 如果node.next 是null的话, right child指向null, 如果不是null, right child则指向root.next的left child
每个节点访问一次 说是时间O(n) 空间O(1)

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.right.next = null;
            }
        }
        connect(root.left);
        connect(root.right);
    }
}

Populating Next Right Pointers in Each Node II leetcode

FFor example,

Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

a这道题的binary tree不一定是完整的 所以root.right.next指向是不定的 思路就是先找到root.right 右边第一个可行node存储
注意这道题应该先遍历右边然后再左边
时间O(n) 空间O(1)

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

Construct Binary Tree from Inorder and Postorder Traversal leetcode

题解：

这道题跟pre+in一样的方法做，只不过找左子树右子树的位置不同而已。 

          1       
         / \   
        2   3   
       / \ / \   
      4  5 6  7

对于上图的树来说，
        index: 0 1 2 3 4 5 6
     中序遍历为: 4 2 5 1 6 3 7
     后续遍历为: 4 5 2 6 7 3 1
为了清晰表示，我给节点上了颜色，红色是根节点，蓝色为左子树，绿色为右子树。
可以发现的规律是：
1. 中序遍历中根节点是左子树右子树的分割点。
2. 后续遍历的最后一个节点为根节点。

同样根据中序遍历找到根节点的位置，然后顺势计算出左子树串的长度。在后序遍历中分割出左子树串和右子树串，递归的建立左子树和右子树。

算法最终相当于一次树的遍历，每个结点只会被访问一次，所以时间复杂度是O(n)。而空间我们需要建立一个map来存储元素到下标的映射，所以是O(n)。
reference: http://www.cnblogs.com/springfor/p/3884035.html

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, map);
    }
    public TreeNode helper(int[] inorder, int instart, int inend, int[] postorder, int postart, int poend, HashMap<Integer, Integer> map) {
        if (instart > inend || postart > poend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[poend]);
        int index = map.get(root.val);
        root.left = helper(inorder, instart, index - 1, postorder, postart,  index - instart + postart - 1, map);
        root.right = helper(inorder, index + 1, inend, postorder, index - instart + postart, poend - 1, map);
        return root;
    }
}

Construct Binary Tree from Preorder and Inorder Traversal leetcode

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

Have you met this question in a real interview? 

Yes

Example

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

  2
 / \
1   3

解：

     1       
    / \   
   2   3   
  / \ / \   
 4  5 6  7

对于上图的树来说，
        index: 0 1 2 3 4 5 6
     先序遍历为: 1 2 4 5 3 6 7 
     中序遍历为: 4 2 5 1 6 3 7
为了清晰表示，我给节点上了颜色，红色是根节点，蓝色为左子树，绿色为右子树。
可以发现的规律是：
1. 先序遍历的从左数第一个为整棵树的根节点。
2. 中序遍历中根节点是左子树右子树的分割点。

再看这个树的左子树：
     先序遍历为: 2 4 5 
     中序遍历为: 4 2 5依然可以套用上面发现的规律。
右子树：
     先序遍历为: 3 6 7 
     中序遍历为: 6 3 7也是可以套用上面的规律的。

所以这道题可以用递归的方法解决。
具体解决方法是：
通过先序遍历找到第一个点作为根节点，在中序遍历中找到根节点并记录index。
因为中序遍历中根节点左边为左子树，所以可以记录左子树的长度并在先序遍历中依据这个长度找到左子树的区间，用同样方法可以找到右子树的区间。
递归的建立好左子树和右子树就好。

 reference:http://www.cnblogs.com/springfor/p/3884034.html

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }
    public TreeNode helper(int[] preorder, int prestart, int preend, int[] inorder, int instart, int inend, HashMap<Integer, Integer> map) {
        if (prestart > preend || instart > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[prestart]);
        int index = map.get(preorder[prestart]);
        root.left = helper(preorder, prestart + 1, index - instart + prestart, inorder, instart, index - 1, map);
        root.right = helper(preorder, index - instart + prestart + 1, preend, inorder, index + 1, inend, map);
        return root;
    }
}

Flatten Binary Tree to Linked List leetcode

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

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

这道题题意就是把树变成linkedlist 但是要以只有右子树的树形式表示出来
用先序遍历, 遍历到的值作为便利到的前一个点的右子树, 前一个点的左子树设为空.
因为递归右子树是在递归左子树之后, 所以root.right会发生变化, 所以root.right要单独存储起来. 便利一次 时间为O(n).

非递归解法就是遇到右子树就入栈， 然后把左子树变成自己的右子树， 左子树设空。 如果没有左子树了， 就从栈里拿出一个当当前node的右子树。

public class Solution {
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        res.add(null);
        helper(res, root);
    }
    public void helper(ArrayList<TreeNode> res, TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode right = root.right;
        if (res.get(0) != null) {
            res.get(0).right = root;
            res.get(0).left = null;
        }
        res.set(0, root);
        helper(res, root.left);
        helper(res, right);
    }
}
//非递归解法 推荐
public class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()) {
            if (p.right != null) {
                stack.push(p.right);
            }
            if (p.left != null) {
                p.right = p.left;
                p.left = null;
            } else if (!stack.isEmpty()) {
                TreeNode tem = stack.pop();
                p.right = tem;
            }
            p = p.right;
        }
    }
}

Symmetric Tree leetcode

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

和same tree那道题思路一样, 终止条件还是1.左子树为空 右子树不为空 2. 右子树为空 左子树不为空 3. 左子树的值和右子树不同
一颗树对称其实就是看左右子树是否对称，一句话就是左同右，右同左，结点是对称的相等。
算法的时间复杂度是树的遍历O(n)，空间复杂度同样与树遍历相同是O(logn)

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return helper(root.left, root.right);
    }
    public boolean helper(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {//if true 继续递归
            return false;
        }
        return helper(node1.left, node2.right) && helper(node2.left, node1.right);
    }
}

Same Tree leetcode

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

这道题是树的题目，属于最基本的树遍历的问题。问题要求就是判断两个树是不是一样，基于先序，中序或者后序遍历都可以做完成，因为对遍历顺序没有要求。这里我们主要考虑一下结束条件，如果两个结点都是null，也就是到头了，那么返回true。如果其中一个是null，说明在一棵树上结点到头，另一棵树结点还没结束，即树不相同，或者两个结点都非空，并且结点值不相同，返回false。最后递归处理两个结点的左右子树，返回左右子树递归的与结果即可。这里使用的是先序遍历，算法的复杂度跟遍历是一致的，如果使用递归，时间复杂度是O(n)，空间复杂度是O(logn)。

reference:http://codeganker.blogspot.com/2014/04/balanced-binary-tree-leetcode.html

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {//p或者q只有一方是null
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Minimum Depth of Binary Tree leetcode

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

如果一个node的左儿子为空 右儿子不空 从root 到左儿子的路径不算是minimum depth
因为左儿子不算这个node的leaf node
所以要比最大深度那道题要多一个判断
如果左儿子空返回右儿子的deepth 右儿子空返回左儿子deepth

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int minDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0) {
            return right + 1;
        }
        if (right == 0) {
            return left + 1;
        }
        return Math.min(left, right) + 1;
    }
}

非递归的做法:

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return res + 1;//node已经算入了 所以要+1 
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res += 1;
        }
        return res;
    }
}

Sum Root to Leaf Numbers leetcode

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

用递归的方法来做, 把根节点到叶子节点所有值加起来, 递归条件是把当前的sum*10 加上子节点的值进行下一轮递归

结束条件是到子节点是空的时候就返回0
算法的本质是一次先序遍历，所以时间是O(n)，空间是栈大小，O(logn)。

public class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);    
    }
    public int helper(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return sum * 10 + root.val;
        }
        int left = helper(root.left, sum*10 + root.val);
        int right = helper(root.right, sum*10 + root.val);
        return left + right;
    }
}

Path Sum II leetcode

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

一般求结果的都用递归求解 这里的时间复杂度仍然只是一次遍历O(n)，而空间复杂度则取决于满足条件的路径和的数量（假设是k条），则空间是O(klogn)。

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

Path Sum leetcode

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

递归(分治)方法来做，递归条件是看左子树或者右子树有没有满足条件的路径，也就是子树路径和等于当前sum减去当前节点的值。结束条件是如果当前节点是空的，则返回false，如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。算法的复杂度是输的遍历，时间复杂度是O(n)，空间复杂度是O(logn)。

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum) {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

Binary Tree Inorder Traversal leetcode

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

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

Inorder: return [1,3,2]. 左中右

addAll 是因为arraylist result 里面应该添加int

第一种是递归的算法，时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。

第二种是迭代的算法， 用栈来实现。 时间复杂度是O(n), 空间O(logn)
第三种是分治算法

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

Binary Tree Zigzag Level Order Traversal leetcode

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

用一个flag记录是否要reverse 一层reverse 一层不reverse添加
判断flag要在for 循环外面
时间O(n) 空间O(n)

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        boolean flag = true;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tem = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (flag) {
                    tem.add(node.val);
                } else {
                    tem.add(0,node.val);
                }
            }
            flag = !flag;
            res.add(tem);
        }
        return res;
    }
}

Binary Tree Level Order Traversal II leetcode

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

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

跟之前题一样， 只是每次添加时候都添加到0位置.做这道题范2了把for循环里的treenode 又起名为root 搞得出错了
第二种方法想法比较简单 但是要声明两次level的组
时间O(n) 空间O(n)

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

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int curlevel = 1;
        int nextlevel = 0;
        ArrayList<Integer> level = new ArrayList<Integer>();
        while (!queue.isEmpty()){
            
            TreeNode cur = queue.poll();
            level.add(cur.val);
            curlevel--;
            if (cur.left != null){
                queue.offer(cur.left);
                nextlevel++;
            }
            if (cur.right != null){
                queue.offer(cur.right);
                nextlevel++;
            }
            if (curlevel == 0){
                curlevel = nextlevel;
                nextlevel = 0;
                result.add(0, level);
                level = new ArrayList<Integer>();
            }
        }
        return result;
    }
}

Binary Tree Level Order Traversal leetcode

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

这道题是广度优先搜索的模板，BFS用queue来实现
时间O(n) 空间O(n)

要注意：a.有while和for双重循环 
b.每次都要给size付一个新值（如果不赋值queue.size在不停变化）
c.queue add 和 delete 是.offer 和.poll 
d. queue为什么用linkedlist实现？？？---Queue是接口， LinkedList可以实现此接口。

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