# 准备工作

## 节点定义

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;
}

}


## 测试

### 二叉树构造

public TreeNode sortedListToBST(List<Integer> list) {
if(list.size() <= 0) {
return null;
}
return generateTree(list, 0, list.size()-1);
}

private TreeNode generateTree(List<Integer> list, int start, int end) {
//此时没有数字，将 null 加入结果中
if(start > end) {
return null;
}
// root 节点
// 1 2 3 4 5
int rootIndex = (start + end)/2;
int rootVal = list.get(rootIndex);
TreeNode treeNode = new TreeNode(rootVal);
// left
treeNode.left = generateTree(list, start, rootIndex-1);
// right
treeNode.right = generateTree(list, rootIndex+1, end);
return treeNode;
}


### 效果

List<Integer> list = Arrays.asList(1,2,3,4,5,6,7);
TreeNode treeNode = tree.sortedListToBST(list);


• 图1 二叉搜索树

leetcode

# 前序遍历

[4, 2, 1, 3, 6, 5, 7]


## 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;
}
// 数据
list.add(treeNode.val);
// 左
if(treeNode.left != null) {
travel(list, treeNode.left);
}
// 右边
if(treeNode.right != null) {
travel(list, treeNode.right);
}
}


### 遍历分析

[4, 2, 1, 3, 6, 5, 7]


## 非递归实现

### 思路

（1）首先访问当前节点 node 的值

（2）node.right 右节点入栈，先进后出。

（3）继续访问 node.left 左节点，如果 left 为空 && 右节点栈不为空，则弹出右节点。

### java 实现

public List<Integer> preorderTraversal(TreeNode root){
List<Integer> lists = new ArrayList<>();
if(root == null){
return lists;
}
Stack<TreeNode> stack = new Stack<>();
//根节点先入栈
stack.push(root);
TreeNode current = null;
while(!stack.isEmpty()){
current = stack.pop();
lists.add(current.val);

//这里注意，要先压入右子结点，再压入左节点。因为栈是先进后出
if(current.right != null){
stack.push(current.right);
}
if(current.left != null){
stack.push(current.left);
}
}
return lists;
}


### 栈信息

public List<Integer> preorderTraversal(TreeNode root){
List<Integer> lists = new ArrayList<>();
if(root == null){
return lists;
}
Stack<TreeNode> stack = new Stack<>();
//根节点先入栈
stack.push(root);
System.out.println("【根节点】root.value="+root.val+" 入栈，STACK " + root);
TreeNode current = null;
while(!stack.isEmpty()){
current = stack.pop();
lists.add(current.val);
System.out.println("\n【出栈】"+current.val+"，STACK " + lists);
System.out.println("【添加】添加 "+current.val+" 到 LIST" + lists);

//这里注意，要先压入右子结点，再压入左节点。因为栈是先进后出
if(current.right != null){
stack.push(current.right);
System.out.println("【右节点】入栈 "+current.right.val+" 到 STACK " + stack);
}
if(current.left != null){
stack.push(current.left);
System.out.println("【左节点】入栈 "+current.left.val+" 到 STACK " + stack);
}
}
return lists;
}


【根节点】root.value=4 入栈，STACK (4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null)))

【出栈】4，STACK []
【添加】添加 4 到 LIST[4]
【右节点】入栈 6 到 STACK [(6: (5: null,null),(7: null,null))]
【左节点】入栈 2 到 STACK [(6: (5: null,null),(7: null,null)), (2: (1: null,null),(3: null,null))]

【出栈】2，STACK [4]
【添加】添加 2 到 LIST[4, 2]
【右节点】入栈 3 到 STACK [(6: (5: null,null),(7: null,null)), (3: null,null)]
【左节点】入栈 1 到 STACK [(6: (5: null,null),(7: null,null)), (3: null,null), (1: null,null)]

【出栈】1，STACK [4, 2]
【添加】添加 1 到 LIST[4, 2, 1]

【出栈】3，STACK [4, 2, 1]
【添加】添加 3 到 LIST[4, 2, 1, 3]

【出栈】6，STACK [4, 2, 1, 3]
【添加】添加 6 到 LIST[4, 2, 1, 3, 6]
【右节点】入栈 7 到 STACK [(7: null,null)]
【左节点】入栈 5 到 STACK [(7: null,null), (5: null,null)]

【出栈】5，STACK [4, 2, 1, 3, 6]
【添加】添加 5 到 LIST[4, 2, 1, 3, 6, 5]

【出栈】7，STACK [4, 2, 1, 3, 6, 5]
【添加】添加 7 到 LIST[4, 2, 1, 3, 6, 5, 7]
[4, 2, 1, 3, 6, 5, 7]


• 图2 前序遍历流程

# 中序遍历

[1, 2, 3, 4, 5, 6, 7]


ps: 这里也可以发现，二叉搜索树的中序遍历，就是一个排序好的链表，此处不做展开。

## 递归实现

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);
}
// 中
list.add(treeNode.val);
// 右边
if(treeNode.right != null) {
travel(list, treeNode.right);
}
}


## 迭代实现

### 思路

（1）当前节点 current 入栈，一直遍历 current.left，如果不为空，全部入栈。直到最左边左子树。(NULL)

（2）弹出栈内信息，访问节点。一开始是最左子树（子节点都是 NULL 的时候），然后是根节点。

（3）访问根节点的 root.right 右节点。

### java 实现

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while(current !=null || !stack.empty()){
// 寻找到最左边的节点
while(current !=null){
stack.add(current);
current = current.left;
}

// pop 处理
current = stack.pop();
list.add(current.val);
current = current.right;
}
return list;
}


### 栈信息

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;

while(current !=null || !stack.empty()){
// 寻找到最左边的节点
while(current !=null){
stack.add(current);
System.out.println("【入栈】当前节点" + current +", STACK: " + stack);
System.out.println("【左子树】继续访问 " +current.val +" 左子树: " + current.left);
current = current.left;
}

// pop 处理
current = stack.pop();
System.out.println("【出栈】当前节点: " + current +", STACK: " + stack);
list.add(current.val);
System.out.println("【添加】添加节点" + current.val +", LIST: " + list);
System.out.println("【右子树】访问节点" + current.val +" 右子树" + current.right + "\n");
current = current.right;
}
return list;
}


【入栈】当前节点(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null))), STACK: [(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null)))]
【左子树】继续访问 4 左子树: (2: (1: null,null),(3: null,null))
【入栈】当前节点(2: (1: null,null),(3: null,null)), STACK: [(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null))), (2: (1: null,null),(3: null,null))]
【左子树】继续访问 2 左子树: (1: null,null)
【入栈】当前节点(1: null,null), STACK: [(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null))), (2: (1: null,null),(3: null,null)), (1: null,null)]
【左子树】继续访问 1 左子树: null
【出栈】当前节点: (1: null,null), STACK: [(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null))), (2: (1: null,null),(3: null,null))]
【添加】添加节点1, LIST: [1]
【右子树】访问节点1 右子树null

【出栈】当前节点: (2: (1: null,null),(3: null,null)), STACK: [(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null)))]
【添加】添加节点2, LIST: [1, 2]
【右子树】访问节点2 右子树(3: null,null)

【入栈】当前节点(3: null,null), STACK: [(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null))), (3: null,null)]
【左子树】继续访问 3 左子树: null
【出栈】当前节点: (3: null,null), STACK: [(4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null)))]
【添加】添加节点3, LIST: [1, 2, 3]
【右子树】访问节点3 右子树null

【出栈】当前节点: (4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null))), STACK: []
【添加】添加节点4, LIST: [1, 2, 3, 4]
【右子树】访问节点4 右子树(6: (5: null,null),(7: null,null))

【入栈】当前节点(6: (5: null,null),(7: null,null)), STACK: [(6: (5: null,null),(7: null,null))]
【左子树】继续访问 6 左子树: (5: null,null)
【入栈】当前节点(5: null,null), STACK: [(6: (5: null,null),(7: null,null)), (5: null,null)]
【左子树】继续访问 5 左子树: null
【出栈】当前节点: (5: null,null), STACK: [(6: (5: null,null),(7: null,null))]
【添加】添加节点5, LIST: [1, 2, 3, 4, 5]
【右子树】访问节点5 右子树null

【出栈】当前节点: (6: (5: null,null),(7: null,null)), STACK: []
【添加】添加节点6, LIST: [1, 2, 3, 4, 5, 6]
【右子树】访问节点6 右子树(7: null,null)

【入栈】当前节点(7: null,null), STACK: [(7: null,null)]
【左子树】继续访问 7 左子树: null
【出栈】当前节点: (7: null,null), STACK: []
【添加】添加节点7, LIST: [1, 2, 3, 4, 5, 6, 7]
【右子树】访问节点7 右子树null


• 图3 中序遍历流程

# 后序遍历

## 流程

[1, 3, 2, 5, 7, 6, 4]

## 递归实现

/**
*
* 【思路】
*
* 左=》右=>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);
}
// 数据
list.add(treeNode.val);
}


## 非递归实现

### 思路

①先序遍历顺序：根节点-左孩子-右孩子

②后序遍历顺序：左孩子-右孩子-根节点

③后序遍历倒过来：根节点-右孩子-左孩子

①和③对比发现，访问顺序只有左孩子和右孩子颠倒了一下

### 前序遍历回顾

public List<Integer> preorderTraversal(TreeNode root){
List<Integer> lists = new ArrayList<>();
if(root == null){
return lists;
}
Stack<TreeNode> stack = new Stack<>();
//根节点先入栈
stack.push(root);
TreeNode current = null;
while(!stack.isEmpty()){
current = stack.pop();
lists.add(current.val);

//这里注意，要先压入右子结点，再压入左节点。因为栈是先进后出
if(current.right != null){
stack.push(current.right);
}
if(current.left != null){
stack.push(current.left);
}
}
return lists;
}


（1）入栈的时候，如何调整左右节点的顺序？

（2）如何反转最后的结果

### java 实现

public List<Integer> postorderTraversal(TreeNode root){
LinkedList<Integer> lists = new LinkedList<>();
if(root == null){
return lists;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode current = null;
while(!stack.isEmpty()){
current = stack.pop();
lists.addFirst(current.val);

if(current.left != null){
stack.push(current.left);
}
if(current.right != null){
stack.push(current.right);
}
}
return lists;
}


### 栈信息

public List<Integer> postorderTraversal(TreeNode root){
LinkedList<Integer> lists = new LinkedList<>();
if(root == null){
return lists;
}

Stack<TreeNode> stack = new Stack<>();
stack.push(root);
System.out.println("【根节点】root.value="+root.val+" 入栈，STACK " + root);
TreeNode current = null;
while(!stack.isEmpty()){
current = stack.pop();
lists.addFirst(current.val);
System.out.println("\n【出栈】"+current.val+"，STACK " + lists);
System.out.println("【添加】添加 "+current.val+" 到 LIST" + lists);

if(current.left != null){
stack.push(current.left);
System.out.println("【左节点】入栈 "+current.left.val+" 到 STACK " + stack);
}
if(current.right != null){
stack.push(current.right);
System.out.println("【右节点】入栈 "+current.right.val+" 到 STACK " + stack);
}
}
return lists;
}


【根节点】root.value=4 入栈，STACK (4: (2: (1: null,null),(3: null,null)),(6: (5: null,null),(7: null,null)))

【出栈】4，STACK [4]
【添加】添加 4 到 LIST[4]
【左节点】入栈 2 到 STACK [(2: (1: null,null),(3: null,null))]
【右节点】入栈 6 到 STACK [(2: (1: null,null),(3: null,null)), (6: (5: null,null),(7: null,null))]

【出栈】6，STACK [6, 4]
【添加】添加 6 到 LIST[6, 4]
【左节点】入栈 5 到 STACK [(2: (1: null,null),(3: null,null)), (5: null,null)]
【右节点】入栈 7 到 STACK [(2: (1: null,null),(3: null,null)), (5: null,null), (7: null,null)]

【出栈】7，STACK [7, 6, 4]
【添加】添加 7 到 LIST[7, 6, 4]

【出栈】5，STACK [5, 7, 6, 4]
【添加】添加 5 到 LIST[5, 7, 6, 4]

【出栈】2，STACK [2, 5, 7, 6, 4]
【添加】添加 2 到 LIST[2, 5, 7, 6, 4]
【左节点】入栈 1 到 STACK [(1: null,null)]
【右节点】入栈 3 到 STACK [(1: null,null), (3: null,null)]

【出栈】3，STACK [3, 2, 5, 7, 6, 4]
【添加】添加 3 到 LIST[3, 2, 5, 7, 6, 4]

【出栈】1，STACK [1, 3, 2, 5, 7, 6, 4]
【添加】添加 1 到 LIST[1, 3, 2, 5, 7, 6, 4]


ps: 当然这个顺序得到的链表是反序的，做一下 reverse 即可。

# 参考资料

https://blog.csdn.net/Monster_ii/article/details/82115772