二叉树前、中、后序遍历、层次遍历

1、前序遍历

• 非递归：利用Stack实现

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

• 递归

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

2、中序遍历

• 非递归：利用Stack实现

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

• 递归：

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

3、后序遍历

• 非递归
  方法一：从根节点开始依次迭代，弹出栈顶元素输出到输出列表中，然后依次压入它的所有孩子节点，按照从上到下、从左至右的顺序依次压入栈中。

因为深度优先搜索后序遍历的顺序是从下到上、从左至右，所以需要将输出列表逆序输出。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {   
        LinkedList<Integer> list = new LinkedList<>();      
        LinkedList<TreeNode> stack = new LinkedList<>();
        if(root ==  null)
            return list;
        stack.add(root);
        while(!stack.isEmpty()){
            root = stack.pollLast();
            list.addFirst(root.val); // 倒序输出
            if(root.left != null)
                stack.add(root.left);
            if(root.right != null)
                stack.add(root.right);
        }
        return list;
    }
}

方法二：使用两个Stack，原理同上，逆序保存在stack2中，在输出道list中

class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
      Stack<TreeNode> stack1 = new Stack<>();
      Stack<Integer> stack2 = new Stack<>();
      stack1.push(root);
      while(!stack1.isEmpty()){
          root = stack1.pop();
          if(root != null){
              stack2.push(root.val);
              stack1.push(root.left);
              stack1.push(root.right);
          }
      }
      ArrayList<Integer> list = new ArrayList<>();
      while(!stack2.isEmpty()){
          list.add(stack2.pop());
      }
      return list;
  }
}

• 递归

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

4、层次遍历

• 非递归：利用Queue实现

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

• 递归

class Solution {
    List<List<Integer>> lastlist = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {   
        if(root == null)
            return lastlist;
        helper(root, 0);
        return lastlist;
    }
    private void helper(TreeNode root, int level){
        if(lastlist.size() == level){
            List<Integer> list = new ArrayList<>();
            lastlist.add(list);
         //lastlist.add(new ArrayList<Integer>());
        }
        lastlist.get(level).add(root.val);
        if(root.left != null)
            helper(root.left, level+1);
        if(root.right != null)
            helper(root.right, level+1);
    }
}