94. Binary Tree Inorder Traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/
先简单回顾下二叉树的遍历，分为先序、中序、后序三种方式，每一种有都有递归和非递归两种方式。先回顾递归的方式。
递归
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
|
public void preOrderRecur(Node head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
public void inOrderRecur(Node head) {
if (head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.value + " ");
inOrderRecur(head.right);
}
public void posOrderRecur(Node head) {
if (head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.value + " ");
}
|
虽然递归方式的代码的样子很简单，但还是需要好好理解的。如果把节点的访问顺序一个个的记录下来，会发现每个节点会访问三次。如果把处理时机放在第一次来到这个节点的时候就是先续遍历，放在第二次就是中序遍历，放在第三次就是后续遍历。
非递归
先序遍历：先将头结点放入栈中，之后在 while 中不断弹出。弹出节点有右节点即将其放入栈中，之后有左子树将其放放入栈中。不使用队列的原因是：先序遍历虽然只能往下走，但是遍历完左子树之后还是需要回去的，所以非递归中序遍历需要用栈结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public void preOrderUnRecur(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
}
|
中序遍历：当前节点一定会把自己的左边界都压到栈里去，其实简略概括为：当前节点不为空，当前节点压入栈，当前节点往左；当前节点为空，从栈顶拿一个打印，当前节点往右边跑。 中序直接从头部节点开始，不需要事先压栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public void inOrderUnRecur(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
}
|
后序遍历：左右中是中右左的逆序，而中左右即为先序遍历，所以中右左是容易实现的。所以可以将中右左弹出的元素压入另一个栈中即可，这就是双栈的做法。单栈的做法不好理解，就不展开了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public void posOrderUnRecur1(Node head) {
if (head != null) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop();
s2.push(head);
if (head.left != null) {
s1.push(head.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
}
|
所以 92 题非递归就是如下的写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
TreeNode p = stack.pop();
result.add(p.val);
root = p.right;
}
}
return result;
}
}
|
589. N-ary Tree Preorder Traversal
https://leetcode.com/problems/n-ary-tree-preorder-traversal/
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
preorder(result, root);
return result;
}
private void preorder(List<Integer> result, Node cur) {
if (cur == null) {
return;
}
result.add(cur.val);
if (cur.children != null && cur.children.size() != 0) {
for (Node child : cur.children) {
preorder(result, child);
}
}
}
|
非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.add(node.val);
if (node.children != null && node.children.size() != 0) {
for (int i = node.children.size() - 1; i >= 0; i--) {
Node child = node.children.get(i);
if (child != null) {
stack.push(child);
}
}
}
}
return result;
}
|
590. N-ary Tree Postorder Traversal
https://leetcode.com/problems/n-ary-tree-postorder-traversal/
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public List<Integer> postorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
postorder(result, root);
return result;
}
private void postorder(List<Integer> result, Node cur) {
if (cur == null) {
return;
}
if (cur.children != null && cur.children.size() != 0) {
for (Node child : cur.children) {
postorder(result, child);
}
}
result.add(cur.val);
}
|
非递归(双栈)
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
| public List<Integer> postorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
Node node = stack1.pop();
stack2.push(node);
if (node.children != null && node.children.size() != 0) {
for (Node child : node.children) {
if (child != null) {
stack1.push(child);
}
}
}
}
while (!stack2.isEmpty()) {
result.add(stack2.pop().val);
}
return result;
}
|
