问题1
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
输出: [1,2,3]
解法
- 对于二叉树的前序遍历，可以简化成对下面这个状态的遍历。
这棵树的遍历过程如下：
- 首先要访问 5
- 然后就是 5 的左孩子，
- 然后就是 5 的右孩子
因此就需要保存 5 这个节点，所以应该使用栈保存下来。再看复杂一点的。
可以总结出规律：
- 节点为空，pop 出一个，访问其右孩子
- 节点不为空，入栈，记录，然后访问其左孩子
1 | /** |
问题2
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
输出: [1,3,2]
- 对于二叉树的中序遍历，可以简化成对下面这个状态的遍历。
这棵树的遍历过程如下：
- 首先过 5
- 然后就是过 5 的左孩子，因为 5的左孩子为 空，所以访问 5
- 然后就是过 5 的右孩子。
因此就需要保存 5 这个节点，所以应该使用栈保存下来。再看复杂一点的。
可以总结出规律：
- 节点为空，pop 出一个，记录，访问其右孩子
- 节点不为空，入栈，然后访问其左孩子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(node != null ||!stack.isEmpty()){
if(node == null){
node = stack.pop();
list.add(node.val);
node = node.right;
}else{
stack.push(node);
node = node.left;
}
}
return list;
}
}
问题3
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
输出: [3,2,1]
- 对于二叉树的中序遍历，可以简化成对下面这个状态的遍历。
- 从右往左，再逆转过来就是后序遍历
- 先过5，并且记录5，然后过 5 的右孩子
- 5 的右孩子为空，过 5 的左孩子
- 5 的左孩子为空
因此就需要保存 5 这个节点，所以应该使用栈保存下来，同时因为5需要 pop,还需要输出栈保存访问路径。再看复杂一点的。
可以总结出规律：
- 节点为空，pop 出一个，访问其左孩子（这里是左孩子）
- 节点不为空，入栈，记录，然后访问其右孩子
- 逆转记录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
TreeNode node = root;
Stack<TreeNode> stack = new Stack<>();
Stack<TreeNode> output = new Stack<>();
while(node != null || !stack.isEmpty()){
if(node == null){
node = stack.pop();
node = node.left;
}else{
stack.push(node);
output.push(node);
//后续+逆转，所以是先 右孩子
node = node.right;
}
}
while(!output.isEmpty()){
list.add(output.pop().val);
}
return list;
}
}