二叉树的遍历
前序遍历
栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
TreeNode curr = root;
while (curr != null || !stk.isEmpty()) {
if (curr != null) {
ans.add(curr.val);
stk.push(curr);
curr = curr.left;
} else {
curr = stk.pop();
curr = curr.right;
}
}
return ans;
}
|
Morris
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
TreeNode curr = root, prev = null;
while (curr != null) {
if (curr.left == null) {
ans.add(curr.val);
curr = curr.right;
} else {
prev = curr.left;
while (prev.right != null && prev.right != curr) {
prev = prev.right;
}
if (prev.right == null) {
ans.add(curr.val);
prev.right = curr;
curr = curr.left;
} else {
prev.right = null;
curr = curr.right;
}
}
}
return ans;
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
TreeNode curr = root;
while (curr != null || !stk.isEmpty()) {
if (curr != null) {
stk.push(curr);
curr = curr.left;
} else {
curr = stk.pop();
ans.add(curr.val);
curr = curr.right;
}
}
return ans;
}
|
Morris
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
TreeNode curr = root, prev = null;
while (curr != null) {
if (curr.left == null) {
ans.add(curr.val);
curr = curr.right;
} else {
prev = curr.left;
while (prev.right != null && prev.right != curr) {
prev = prev.right;
}
if (prev.right == null) {
prev.right = curr;
curr = curr.left;
} else {
prev.right = null;
ans.add(curr.val);
curr = curr.right;
}
}
}
return ans;
}
|
后序遍历
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
| public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Stack<TreeNode> stk = new Stack<>();
TreeNode prev = root, curr = root;
while (curr != null || !stk.isEmpty()) {
if (curr != null) {
stk.push(curr);
curr = curr.left;
} else {
curr = stk.pop();
if (curr.right == null || curr.right == prev) {
ans.add(curr.val);
prev = curr;
curr = null;
} else {
stk.push(curr);
curr = curr.right;
}
}
}
return ans;
}
|
判断完全二叉树的结点个数
递归，当二叉树的左右深度不一样的时候，它一定不是满二叉树，但是完全二叉树的子树一定是完全二叉树，因此可以递归计算子树的节点数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
TreeNode left = root.left;
TreeNode right = root.right;
int leftLevel = 0;
while (left != null) {
leftLevel++;
left = left.left;
}
int rightLevel = 0;
while (right != null) {
rightLevel++;
right = right.right;
}
if (leftLevel == rightLevel) {
return (1 << (leftLevel + 1)) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
|