# 统一节点定义

public class TreeNode {

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

}


# 中序遍历

https://leetcode.com/problems/binary-tree-inorder-traversal

## 递归实现

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> results = new ArrayList<>();
travel(results, root);
return results;
}

private void travel(List<Integer> list, TreeNode treeNode) {
if(treeNode == null) {
return;
}
// 左
if(treeNode.left != null) {
travel(list, treeNode.left);
}
// 中
// 右边
if(treeNode.right != null) {
travel(list, treeNode.right);
}
}


## 迭代实现

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}


# 前序遍历

## java 实现

/**
*
* 【思路】
*
* 数据=》左=》右
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Preorder Traversal.
* Memory Usage: 37 MB, less than 89.16% of Java online submissions for Binary Tree Preorder Traversal.
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> results = new ArrayList<>();
travel(results, root);
return results;
}

private void travel(List<Integer> list, TreeNode treeNode) {
if(treeNode == null) {
return;
}
// 数据
// 左
if(treeNode.left != null) {
travel(list, treeNode.left);
}
// 右边
if(treeNode.right != null) {
travel(list, treeNode.right);
}
}


## 非递归实现

public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}


# 后序遍历

## 递归实现

/**
*
* 【思路】
*
* 左=》右=>D
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Postorder Traversal.
* Memory Usage: 37.7 MB, less than 19.80% of Java online submissions for Binary Tree Postorder Traversal.
*
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> results = new ArrayList<>();
travel(results, root);
return results;
}
private void travel(List<Integer> list, TreeNode treeNode) {
if(treeNode == null) {
return;
}
// 左
if(treeNode.left != null) {
travel(list, treeNode.left);
}
// 右边
if(treeNode.right != null) {
travel(list, treeNode.right);
}
// 数据
}


## 非递归实现

public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val);  // Reverse the process of preorder
p = p.right;             // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left;           // Reverse the process of preorder
}
}
return result;
}


# 层序遍历

## 题目

二叉树：[3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

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


## 解法一：前序遍历

### java 实现

public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
levelOrder(results, root, 0);
return results;
}

private void levelOrder(List<List<Integer>> results, TreeNode treeNode, int level) {
if(treeNode == null) {
return;
}
// 当前节点
// AVOID BOUND EX
if(results.size() <= level) {
}
List<Integer> list = results.get(level);
// 节点
int val = treeNode.val;
results.set(level, list);
// 左
levelOrder(results, treeNode.left, level+1);
// 右
levelOrder(results, treeNode.right, level+1);
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Level Order Traversal.
Memory Usage: 39.2 MB, less than 56.89% of Java online submissions for Binary Tree Level Order Traversal.


# 从下往上的层序遍历

## 题目

二叉树：[3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

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


（1）获取层序遍历的列表

（2）列表反序

## 实现

public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
levelOrder(results, root, 0);
// reverse
return reverseList(results);
}

private List<List<Integer>> reverseList(List<List<Integer>> list) {
if(list.size() <= 1) {
return list;
}
// 从后向前遍历
List<List<Integer>> results = new ArrayList<>();
for(int i = list.size()-1; i >= 0; i--) {
List<Integer> temp = list.get(i);
}
return results;
}

private void levelOrder(List<List<Integer>> results, TreeNode treeNode, int level) {
if(treeNode == null) {
return;
}
// 当前节点
// AVOID BOUND EX
if(results.size() <= level) {
}
List<Integer> list = results.get(level);
// 节点
int val = treeNode.val;
results.set(level, list);
// 左
levelOrder(results, treeNode.left, level+1);
// 右
levelOrder(results, treeNode.right, level+1);
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Level Order Traversal.
Memory Usage: 39.2 MB, less than 56.89% of Java online submissions for Binary Tree Level Order Traversal.


# 层级 Z 字形遍历

## 题目

给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

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


## 实现如下

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
levelOrder(results, root, 0);
// 根據層級進行反轉
reverseByLevel(results);
return results;
}

private void reverseByLevel(List<List<Integer>> results) {
if(results.size() <= 1) {
return;
}
// 偶數開始便利
for(int i = 1; i < results.size(); i+=2) {
List<Integer> list = results.get(i);
Collections.reverse(list);
results.set(i, list);
}
}

/**
*
* @param results 結果
* @param treeNode 樹
* @param level 層級
*/
private void levelOrder(List<List<Integer>> results, TreeNode treeNode, int level) {
if(treeNode == null) {
return;
}
// 当前节点
// AVOID BOUND EX
if(results.size() <= level) {
}
List<Integer> list = results.get(level);
// 节点
int val = treeNode.val;
results.set(level, list);
// 左
levelOrder(results, treeNode.left, level+1);
// 右
levelOrder(results, treeNode.right, level+1);
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
Memory Usage: 39.2 MB, less than 50.08% of Java online submissions for Binary Tree Zigzag Level Order Traversal.


# 参考资料

https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/Preorder-Inorder-and-Postorder-Iteratively-Summarization

102. 二叉树的层序遍历