樹節點的基本結構：

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
    }
  }

1.先序遍歷：

遍歷順序：根-左孩子-右孩子

1.1 遞歸算法：

class Solution {
    List res;
    public List preorderTraversal(TreeNode root) {
        res = new LinkedList();
        preTraver(root);
        return res;
    }
    public void preTraver(TreeNode root) {
        if(root != null) {
            res.add(root.val);
            preTraver(root.left);
            preTraver(root.right);
        }
    }
}

1.2 非遞歸算法：

使用棧來做。最外面用root變量來保存左孩子。root不為空，則直接入棧，并記錄下當前值（因為先序遍歷是先遍歷根）；如果root為空，說明此時棧頂結點應該遍歷右孩子，則出棧，并遍歷右孩子。

class Solution {
    List res;
    public List preorderTraversal(TreeNode root) {
        Deque stack = new LinkedList();
        List res = new ArrayList();
        while(root!=null || !stack.isEmpty()) {
            if(root != null) {
                stack.addFirst(root);
                res.add(root.val);
                root = root.left;
            } else {
                TreeNode p = stack.pollFirst();
                if(p.right != null) {
                    root = p.right;
                }
            }
        }
        return res;
    }
}

2.中序遍歷

遍歷順序：左孩子-根-右孩子

2.1 遞歸算法：

使用棧來做。最外面用root變量來保存左孩子。root不為空，則直接入棧；如果root為空，說明此時棧頂結點應該遍歷右孩子。

class Solution {
    List res;
    public List inorderTraversal(TreeNode root) {
        res = new ArrayList();
        inorderTraver(root);
        return res;
    }
    public void inorderTraver(TreeNode root) {
        if(root != null) {
            inorderTraver(root.left);
             res.add(root.val);
            inorderTraver(root.right);
           
        }
    }
}

2.2 非遞歸算法：

使用棧來做。最外面用root變量來保存左孩子。root不為空，則直接入棧；如果root為空，說明此時棧頂結點應該遍歷右孩子，則出棧，記錄下當前結點的值（因為中序遍歷是先遍歷左孩子，然后才是根），然后遍歷右孩子。

與先序遍歷基本相同，唯一不同的地方在于何時記錄結點值。先序遍歷是入棧的時候記錄結點值，中序遍歷時出棧的時候記錄結點值。

class Solution {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stack = new LinkedList();
        while(root!=null || !stack.isEmpty()) {
            if(root != null) {
                stack.addFirst(root);
                root = root.left;
            } else {
                TreeNode p = stack.poll();
                res.add(p.val);
                root = p.right;
            }
        }
        return res;
    }
}

3. 后序遍歷

遍歷順序：左孩子-右孩子-根

3.1 遞歸算法

class Solution {
    List res;
    public List postorderTraversal(TreeNode root) {
        res = new ArrayList();
        posTraver(root);
        return res;
    }
    public void posTraver(TreeNode root) {
        if(root != null) {
            posTraver(root.left);
            posTraver(root.right);
            res.add(root.val);
        }
    }
}

3.2 非遞歸算法

考慮到，先序遍歷是（根-左孩子-右孩子）、后序遍歷是（左孩子-右孩子-根）因此可以再先序遍歷的基礎上進行改進，改成（根-右孩子-左孩子），然后進行逆置操作。對于ArraList可以采用Collections.reverse(res)來進行逆置。

class Solution {
    
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        Deque stack = new LinkedList();
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                stack.addFirst(root);
                res.add(root.val);
                root = root.right;
            } else {
                TreeNode p = stack.pollFirst();
                root = p.left;
            }
        }
        Collections.reverse(res);
        return res;
    }
}

4. 層序遍歷

4.1 遞歸算法

記錄下當前結點位于第幾層，先后遍歷左右結點。

class Solution {
    List> res;
    public List> levelOrder(TreeNode root) {
        res = new ArrayList>();
        if(root == null) {return res;}
        levelTravel(root, 0);
        return res;
    }
    public void levelTravel(TreeNode root, int level) {
        if(root == null) {
            return ;
        } 
        List temp ;
        if(level >= res.size()) {
          temp  = new ArrayList();
          res.add(temp);
        } else {
            temp = res.get(level);
        }
        temp.add(root.val);
        levelTravel(root.left,level +1);
        levelTravel(root.right,level +1);
        
    }
}

4.2? 非遞歸算法

采用隊列來做。

class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList>();
        if(root == null) {return res;}
        Deque queue = new LinkedList();
        queue.addFirst(root);
        int n = 1;
        while(!queue.isEmpty()) {
            n = queue.size();
            List temp = new ArrayList();
            for(int i = 1; i <= n; i++) {
                TreeNode p = queue.pollLast();
                temp.add(p.val);
                if(p.left != null) {
                    queue.addFirst(p.left);
                } 
                if(p.right != null) {
                    queue.addFirst(p.right);
                } 
            }
            res.add(temp);
        }
        return res;
    }
}