二叉树的递归遍历
二叉树的递归遍历
前序中序后序遍历其实就是二叉树中的深度优先遍历，层序遍历是广度优先遍历
前序遍历（中左右）
前序遍历的顺序是中左右。
前序遍历的过程是：先一条路先走到头，然后回到上一个岔路口走上一条没走过的岔路，走完之后再回到上上个岔路。
回溯算法，也是这个顺序，前序遍历。
代码
其中树节点实现了 BTPrinterAdapter，具体请看 在控制台输出二叉树的结构
public class Traverse {
private static int index = 1;
public TreeNode constructNode() {
TreeNode node = new TreeNode(1);
node.left = new TreeNode(2);
node.right = new TreeNode(3);
node.left.left = new TreeNode(4);
node.left.right = new TreeNode(5);
node.right.left = new TreeNode(6);
node.right.right = new TreeNode(7);
node.left.left.left = new TreeNode(8);
node.left.left.right = new TreeNode(9);
node.left.right.left = new TreeNode(10);
node.left.right.right = new TreeNode(11);
node.right.left.left = new TreeNode(12);
node.right.left.right = new TreeNode(13);
node.right.right.left = new TreeNode(14);
node.right.right.right = new TreeNode(15);
return node;
}
public static void main(String[] args) {
index = 1;
TreeNode node = new Traverse().constructNode();
BTPrinter.printTree(node);
System.out.println("==========================");
List<Integer> result = new Traverse().traverse(node);
System.out.println(Arrays.toString(result.toArray()));
System.out.println("==========================");
BTPrinter.printTree(node);
}
public List<Integer> traverse(TreeNode node) {
List<Integer> result = new ArrayList<>();
if (node == null) {
return result;
}
result.add(node.val);
node.index = index++;
result.addAll(traverse(node.left));
result.addAll(traverse(node.right));
return result;
}
public class TreeNode implements BTPrinterAdapter<TreeNode> {
public int val;
public TreeNode left;
public TreeNode right;
public int index;
public TreeNode(int x) {
val = x;
}
@Override
public String toString() {
return "TreeNode{" +
"val=" + val +
'}';
}
@Override
public String getNodeString() {
String valStr = String.valueOf(val);
if (index > 0) {
valStr += "--" + String.valueOf(index);
}
return valStr;
}
@Override
public TreeNode getLeftNode() {
return left;
}
@Override
public TreeNode getRightNode() {
return right;
}
}
}
执行之后，输出
-------------------------------------------------
1
____________| |____________
2 3
____| |_____ _____| |_____
4 5 6 7
_| |_ _| |_ _| |_ _| |_
8 9 10 11 12 13 14 15
==========================
[1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]
==========================
----------------------------------------------------------------------------------------------------
1--1
_____________________| |________________________
2--2 3--9
_______| |________ _________| |_________
4--3 5--6 6--10 7--13
_| |_ _| |_ _| |_ _| |_
8--4 9--5 10--7 11--8 12--11 13--12 14--14 15--15
只看树上的节点遍历顺序
中序遍历（左中右）
遍历顺序是左中右
代码
只需要将上一个小结的代码中的 traverse 方法换成
public List<Integer> traverse(TreeNode node) {
List<Integer> result = new ArrayList<>();
if (node == null) {
return result;
}
result.addAll(traverse(node.left));
result.add(node.val);
node.index = index++;
result.addAll(traverse(node.right));
return result;
}
输出
-------------------------------------------------
1
____________| |____________
2 3
____| |_____ _____| |_____
4 5 6 7
_| |_ _| |_ _| |_ _| |_
8 9 10 11 12 13 14 15
==========================
[8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]
==========================
----------------------------------------------------------------------------------------------------
1--8
_____________________| |_______________________
2--4 3--12
_______| |________ _________| |_________
4--2 5--6 6--10 7--14
_| |_ _| |_ _| |_ _| |_
8--1 9--3 10--5 11--7 12--9 13--11 14--13 15--15
只看树上的节点遍历顺序
可以看到最先得到遍历的是整棵树最左边的节点。假设有一根竖线从左到右扫整个树，你会发现其扫过的节点的顺序，起始就是中序遍历。
如果这个二叉树，恰好是二叉搜索树（右节点大于中间节点大于左子节点），那么中序遍历的结果就是将整个树输出为一个递增的序列。我们可以用这个特性快速检验一个二叉树是不是二叉搜索树。例如 98. 验证二叉搜索树。
后续遍历（左右中）
遍历顺序是左右中
代码
只需要将上一个小结的代码中的 traverse 方法换成
public List<Integer> traverse(TreeNode node) {
List<Integer> result = new ArrayList<>();
if (node == null) {
return result;
}
result.addAll(traverse(node.left));
result.addAll(traverse(node.right));
result.add(node.val);
node.index = index++;
return result;
}
输出
-------------------------------------------------
1
____________| |____________
2 3
____| |_____ _____| |_____
4 5 6 7
_| |_ _| |_ _| |_ _| |_
8 9 10 11 12 13 14 15
==========================
[8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1]
==========================
----------------------------------------------------------------------------------------------------
1--15
_____________________| |______________________
2--7 3--14
_______| |________ ________| |_________
4--3 5--6 6--10 7--13
_| |_ _| |_ _| |_ _| |_
8--1 9--2 10--4 11--5 12--8 13--9 14--11 15--12
只看树上的节点遍历顺序
可以注意到整棵树最左边的节点最先遍历，整个树的根节点最后被遍历。
通过中序遍历和前序或者后序遍历恢复整个二叉树
105. 从前序与中序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
前序和后序可以恢复一个二叉树吗？
前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
那么前序和后序可不可以唯一确定一棵二叉树呢？
前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。
举个反例就行了
tree1 的前序遍历是 [1 2 3]， 后序遍历是 [3 2 1]。
tree2 的前序遍历是 [1 2 3]， 后序遍历是 [3 2 1]。
那么 tree1 和 tree2 的前序和后序完全相同，这是一棵树么，很明显是两棵树！
所以前序和后序不能唯一确定一棵二叉树！
不同的遍历顺序的用处
当我们要从下往上便利的时候，根据子节点过滤父节点的时候，比如 236. 二叉树的最近公共祖先，我们就应该选择后序便利
当我们碰到二叉搜索树的时候，中序遍历可以将其输出为一个递增的序列。
遍历方式不止这三种
不要因为我们老是使用使用这三种方式，写习惯了这三种方式，就认为二叉树就只有这三种遍历方式：前序（中左右），中序（左中右），后序遍历（左右中），不要让思维已经形成定势，其实我们还可以反过来，右左中，右中左，中右左。
比如 538. 把二叉搜索树转换为累加树。