二叉树的遍历

问题1

二叉树的前序遍历，递归和非递归

原理

• 根左右

代码

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

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

注意事项

• 牢记二叉树的遍历口诀，前序根左右，中序左根右，后序左右根。

问题2

二叉树的中序遍历，递归和非递归

原理

• 中序左根右

代码

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

}

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        
        if(root==null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
       TreeNode cur = root;

       while(cur!=null||!stack.isEmpty()){
           while(cur!=null){
               stack.add(cur);
               cur = cur.left;
           }
            TreeNode mid =  stack.pop();
            list.add(mid.val);
            cur = mid.right;
           
       }
        return list;
    }

}

注意事项

问题3

二叉树的后序遍历，递归和非递归

原理

• 左右根

代码

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        
        if(root==null){
            return list;
        }

        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);

        return list;
    }
}

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        
        if(root==null){
            return list;
        }

        Stack<TreeNode>  stack = new Stack<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur.left!=null){
                stack.add(cur.left);
            }
            if(cur.right!=null){
                stack.add(cur.right);
            }
            list.add(cur.val);
        }

        Collections.reverse(list);

        return list;
    }
}

注意事项

• 先按照左右根入栈，出来的顺序应该是根右左
• 然后把根右左reverse，变成左右根。

问题4

二叉树的层序遍历，递归和非递归

原理

• 先进先出，自然想到队列。
• 按照层迭代。

代码

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

注意事项

• 处理每一层的元素需要使用循环。

问题5

二叉树的之字形遍历，递归和非递归

原理

• 原理和问题5一致，就是考虑一下奇偶问题就好了。

代码

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.add(root);
         int count = 0;
         while(!q.isEmpty()){
             int size = q.size();
             LinkedList<Integer> clist = new LinkedList<>();
             for(int i=0;i<size;i++){
                 TreeNode cur = q.poll();
                 if(cur.left!=null){
                     q.add(cur.left);
                 }
                 if(cur.right!=null){
                     q.add(cur.right);
                 }
                 if(count%2==0){
                     clist.addLast(cur.val);
                 }else{
                     clist.addFirst(cur.val);
                 }
             }
             res.add(new LinkedList<>(clist));
             count++;
         }
         return res;
    }
}

注意事项

• 采用一个变量count来记录是odd还是even。
• 使用linkedlist的特性，addlast or addFirst