二叉树的前序遍历
这次准备来复习一下二叉树的各种遍历以及实现方法。
Leetcode上的第144题就是二叉树的前序遍历，前序遍历即根左右的遍历方式首先我能想到最简单的方法当然就是递归了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) return res;
preorderTraversal(root, res);
return res;
}
public void preorderTraversal(TreeNode node, ArrayList<Integer> res) {
if (node == null) return;
res.add(node.val);
preorderTraversal(node.left, res);
preorderTraversal(node.right, res);
}
}
|
第二种方法当然就是迭代了，迭代的话需要用一个栈来确保节点的出入顺序，下面的是代码实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return res;
while (root != null || !stack.isEmpty()) {
if (root != null) {
res.add(root.val);
stack.push(root);
root = root.left;
continue;
}
root = stack.pop();
root = root.right;
}
return res;
}
}
|
迭代相比递归来说难的点就是需要自己控制节点的顺序。让我来详细解释以下前序遍历迭代法的实现思路。
前序遍历是先遍历根节点，再遍历左节点，最后遍历右节点。所以我这里在节点入栈的时候就将根节点加入到结果数组中，直接遍历，当_root_为null就代表左子树我们已经遍历完毕了。于是我们弹出栈中的元素，并继续遍历这个元素的右子树。
二叉树的中序遍历
Leetcode94题为二叉树的中序遍历。中序遍历相比于前序遍历多了一种空间复杂度为O(1)的Morris方法。
最简单也是最容易想到的就是递归法了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> ans = new ArrayList<>();
if (root == null) return ans;
inorderTraversal(root.left, ans);
ans.add(root.val);
inorderTraversal(root.right, ans);
return ans;
}
public void inorderTraversal(TreeNode node, List<Integer> ans) {
if (node == null) return;
inorderTraversal(node.left, ans);
ans.add(node.val);
inorderTraversal(node.right, ans);
}
}
|
递归法也没有什么好说的，就是正常思维，先遍历左子树，在再遍历根节点，最后遍历右子树。
第二种方法就是迭代了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> ans = new ArrayList<>();
if (root == null) return ans;
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
ans.add(root.val);
root = root.right;
}
return ans;
}
|
思路解读
中序遍历的迭代法我们又应该怎么思考呢。中序遍历我们不能和前序遍历一样在root = root.left的循环中直接将root节点加入到结果数组中。我们必须要找到整个二叉树的最左边的节点，然后pop出节点，在添加到结果数组中。然后再遍历这个节点的右子树，如果没有右子树，那就弹出下一个节点，继续添加到结果数组中。
第三种方法就是Morris遍历算法，空间复杂度可以达到O(1)的级别。
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
| public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
TreeNode predecessor = null;
while (root != null) {
if (root.left != null) {
predecessor = root.left;
while (predecessor.right != null && predecessor.right != root) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = root;
root = root.left;
} else {
res.add(root.val);
predecessor.right = null;
root = root.right;
}
} else {
res.add(root.val);
root = root.right;
}
}
return res;
}
|
思路解读
这种思路有点像模拟法。我们来思考以下，root的上一个节点这里说的上一个节点是中序遍历的上一个节点是什么，其实就是root.left这个节点所在的整个二叉树的最右边的节点。**这是Morris遍历算法实现的最核心的思维。通过遍历将predecessor的右指针指向root，以此来实现中序遍历。
二叉树的后序遍历
Leetcode145是二叉树的后序遍历。
第一种方法也是最容易想到的就是递归了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) return res;
postorderTraversal(root, res);
return res;
}
public void postorderTraversal(TreeNode node, List<Integer> res) {
if (node == null) return;
postorderTraversal(node.left, res);
postorderTraversal(node.right, res);
res.add(node.val);
}
|
第二种方法就是迭代，我们依然需要用栈来实现。
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> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
}else {
stack.push(root);
root = root.right;
}
}
return res;
}
|
说实话，后序遍历的迭代实现比前序遍历和中序遍历都要复杂一些。思路如下
后序遍历为左，右，根的顺序遍历。所以判断条件要复杂一些。前面是一样的，在root=root.left的循环中入栈。当root==null的时候，弹出第一个节点，判断这个节点的右子树是否为null，如果不为null,则将此节点入栈，然后将root.right入栈，如果这个节点的右节点为null或者为前一个加入到结果数组的节点，则将这个节点添加到结果数组中。
问题:为什么需要一个节点来表示上一个加入到结果数组的节点?
解释：左、右、根的顺序，当我们遍历到根节点的时候，节点的右子树并不为null，但是我们不能重复添加，所以还需要这一层判断。
二叉树的层序遍历
Leetcode102为二叉树的层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> res = new ArrayList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
if (root == null) return res;
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(list);
}
return res;
}
|
思路解释
我们需要一个FIFO队列来实现二叉树的层序遍历。每次遍历的时候遍历一层的节点，节点的数量就是queue.size()。然后再poll出levelSize数量的节点，在遍历过程中，如果遍历节点的左、右节点不为null，则将其入队。
层序遍历只要理解其思想还是很简单的。