LeetCode 之二叉树的各种遍历(Binary Tree Traversal)

在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

想必大家对二叉树也不陌生,被各种二叉树面试题支配的恐惧仍记忆犹新……

这篇就总结一下二叉树的各种遍历,包括前、中、后序遍历还有层次遍历。

让我们来想象,大脑是个无底洞,这个栈它没有深度,所以我们要时而把栈底那些强行挖上来,以防痴呆!你不想痴呆吧!go go go.

层次遍历

先来这个层次遍历,二叉树一层又一层,它有深度。既然是一层接着一层,那很清楚了,我们逐层遍历就行。

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回其层次遍历结果:

[
[3],
[9,20],
[15,7]
]

清晰得不能再清晰了。递归调用 + 循环节点。代码如下:

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
38
39
40
41
42
43
44
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> list = new ArrayList<>();
List<TreeNode> l = new ArrayList<>();
l.add(root);
helper(list, l);
return list;

}

/**
* 递归 层层遍历
*
* @param list
* @param treeList
*/
private void helper(List<List<Integer>> list, List<TreeNode> treeList) {
if (treeList.size() == 0)
return;
List<Integer> listInt = new ArrayList<>();
List<TreeNode> treeL = new ArrayList<>();
// 逐层添值
for (TreeNode node : treeList) {
if (node != null) {
listInt.add(node.val);
treeL.add(node.left);
treeL.add(node.right);
}
}
if (listInt.size() > 0)
list.add(listInt);

helper(list, treeL);
}

或者是使用队列 + while 循环搞定:

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
/**
* 使用队列 queue
*
* @param root
* @return
*/
public List<List<Integer>> levelOrder1(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

if (root == null)
return wrapList;

queue.offer(root);
while (!queue.isEmpty()) {
// 有值就塞入集合 同时将其左右子节点添加到队列中
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for (int i = 0; i < levelNum; i++) {
if (queue.peek().left != null)
queue.offer(queue.peek().left);
if (queue.peek().right != null)
queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(subList);
}
return wrapList;
}

这个问题不大。

中序遍历

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

也就是根结点遍历位置在中间: 左 -> 根 -> 右

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

既然都说了递归算法很简单,确实也很简单,先上递归算法:

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
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

/**
* 递归
*
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
helper(list, root);
return list;
}

private void helper(List<Integer> list, TreeNode node) {
if (node != null) {
if (node.left != null)
helper(list, node.left);
list.add(node.val);
if (node.right != null)
helper(list, node.right);
}
}

这个递归算法在前、中、后序遍历都可以套用的,着实好用也好记。下面就不重复该代码了,无非就是结点的顺序换一换。

迭代算法,这里我们思考一下,我们需要先读其左结点,读完之后再读其根结点,左结点若是存在,那它不就是下一层的根结点吗?然后我们再一层层往上读。此时脑壳一抖,栈!

Stack 来解决:

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
/**
* 栈 stack 来解决
*
* @param root
* @return
*/
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
// 将其左节点依次放入 因为先读左节点
stack.push(curr);
curr = curr.left;
}
// 将栈顶弹出
curr = stack.pop();
// 塞值
res.add(curr.val);
// 将右节点赋值给它 完美呈现了中序遍历 : 左 -> 根 -> 右
curr = curr.right;
}
return res;
}

代码也不长,该过程可以用大脑无底栈来走一遍。闭上眼睛,冥想。

前序遍历

前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

即根结点遍历位置在前面: 根 -> 左 -> 右

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个二叉树,返回它的 前序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

递归算法不说了,见上。

迭代这里用双向链表 LinkedList,数据量大时存取数据性能好点。

代码如下:

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
/**
* 双向队列
*
* @param root
* @return
*/
public List<Integer> preorderTraversal1(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
// 弹出队列中最后一个
TreeNode node = stack.pollLast();
output.add(node.val);
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
// 该节点就是下一个要读的根节点
stack.add(node.left);
}
}
return output;
}

这里需要注意的就是 stack.add() 先添加右结点在添加左结点,因为 stack.pollLast() 取出的是最后一个数据,这样就是左结点先弹出,满足前序遍历的顺序。

后序遍历

后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。

即根结点遍历位置在前面: 左 -> 右 -> 根

题目描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个二叉树,返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

同样,递归算法不重复,见上。

这里的迭代算法我是看了官网的解法。秒。利用双向链表每次在起始位置添加值,顺序为根 -> 右 -> 左,然后遍历完后整个顺序从前往后就是左 -> 右 -> 根,后序遍历。

双向链表 LinkedList + 栈 Stack,代码如下:

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
38
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

/**
* 根 -> 右 -> 左 存入,遍历完全后从前往后即是 左 -> 右 -> 根
*
* @param root
* @return
*/
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null)
return ans;

stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
// 将值塞到最前面
ans.addFirst(cur.val);
// 先左结点入栈
if (cur.left != null) {
stack.push(cur.left);
}
// 再是右结点入栈
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}

从后往前推,一气呵成。


其实,还是递归最好使……

文章作者: Folgerjun
文章链接: http://putop.top/2018/11/27/leetcode-binary-tree-traversal/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 DoubleFJ の Blog