前言
最近在看面试题，基本已经知道算法这块地方是自己的薄弱点，特意复习记录一下。
今天写的是二叉树的前中后序遍历，我会分别用递归还有迭代的方法实现。
正文
前序遍历
来源LeetCode第144题。
递归
官方特意在题目中标注递归算法很简单，那么就先来看看递归算法。
递归算法就是先得到结点值，然后递归遍历左子树和右子树。
python代码如下
1
2
3
4
5
6
7
8
9
10
| class Solution:
def preorderTraversal(self,root):
if not root:
return []
result = []
result.append(root.val)
result.extend(self.preorderTraversal(root.left))
result.extend(self.preorderTraversal(root.right))
return result
|
Java代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
List<Integer> result = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return result;
}
public void preOrder(TreeNode root){
if(root == null){
return;
}
result.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
}
|
与python大同小异。
迭代
我们知道递归的本质是使用栈来实现，那么我们也可以使用一个栈来帮助我们进行迭代。
而栈的进入顺序为先右子树然后左子树，因为栈是先进后出的数据结构，所以我们让右子树先进栈，让左子树先出栈，才能实现root-left-right的顺序。
python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution(object):
def preorderTraversal(self, root):
if not root:
rerurn []
stack = []
result = []
stack.append(root)
while stack:
node = stack.pop()
if not node:
continue
result.append(node.val)
stack.append(node.right)
stack.append(node.left)
return result
|
Java代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList<Integer>();
}
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
result.add(temp.val);
if(temp.right != null){
stack.push(temp.right);
}
if(temp.left != null){
stack.push(temp.left);
}
}
return result;
}
}
|
中序遍历
来自LeetCode第94题。
中序遍历是left-root-right的顺序，递归方法依旧很简单。
递归
python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def inorder(root):
if root == None:
return
if root.left != None:
inorder(root.left)
res.append(root.val)
if root.right != None:
inorder(root.right)
inorder(root)
return res
|
其实可以省略判断，因为函数开始就已经判断root是否为空。
Java代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
helper(root,result);
return result;
}
public void helper(TreeNode root,List<Integer> result){
if (root == null){
return;
}
helper(root.left,result);
result.add(root.val);
helper(root.right,result);
return;
}
}
|
迭代
中序遍历的迭代方法与前序遍历难一些。中序遍历需要先将所有左子树压入栈中，然后开始从二叉树左下角的节点开始出栈，将本节点的的值放入结果中，然后将该节点的右子树放入栈中。之后便可按照left-root-right的顺序将值放入结果中。
python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
stack = []
res = []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return res
root = stack.pop()
res.append(root.val)
root = root.right
|
Java代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> result = new ArrayList<>();
while (true){
while (root != null){
stack.push(root);
root = root.left;
}
if (stack.isEmpty()){
return result;
}
root = stack.pop();
result.add(root.val);
root = root.right;
}
}
}
|
我们可以稍微修改下代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty() || root != null){
if (root != null){
stack.push(root);
root = root.left;
}else{
root = stack.pop();
result.add(root.val);
root = root.right;
}
}
return result;
}
}
|
后序遍历
LeetCode第145题。前中后序遍历官方给的难度是递增的。后序遍历难度为困难。
递归
当然我们如果使用递归的话就比较简单。与前序中序相似，只改变一下节点值加入结果的顺序。
python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def postorder(root):
if root == None:
return
if root.left != None:
postorder(root.left)
if root.right != None:
postorder(root.right)
res.append(root.val)
inorder(root)
return res
|
Java代码类似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
helper(root,result);
return result;
}
public void helper(TreeNode root,List<Integer> result){
if (root == null){
return;
}
helper(root.left,result);
helper(root.right,result);
result.add(root.val);
return;
}
}
|
迭代
困难主要在于使用迭代实现后序遍历。后序遍历的顺序为left-right-root，由于我们先获得的是root节点，之后才能获取左右子树，所以我们改变思路，
我们可以先从root-right-left的顺序下手，之后再反序，就可以得到后序遍历的结果。
由于我们使用的是栈，我们先把根节点放入栈中，然后依次放入左子树和右子树，这样栈的弹出顺序就是由右子树到左子树，那么我们的思路就确定了：
先将根节点push到栈中，pop出来后将值存入结果中，然后分别push左右子树到栈中，右子树先出栈，得到了右子树的值，然后得到左子树的值，即遍历顺序就为根-右子树-左子树。
因此，我们的入栈顺序就是为root-left-right
python代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
stack = [root]
res = []
if not root:
return []
while stack:
node = stack.pop()
if not node:
continue
res.append(node.val)
stack.append(node.left)
stack.append(node.right)
return res[::-1]
|
Java代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null){
return new ArrayList<Integer>();
}
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
if (temp == null){
continue;
}
result.add(temp.val);
stack.push(temp.left);
stack.push(temp.right);
}
Collections.reverse(result);
return result;
}
}
|
总结
这次总结了三种二叉树的遍历方式，相比于之前，确实又加深了不少理解。三种遍历方式使用递归方法都非常简单，但是使用迭代方法就有些难度了，
其中前序遍历最简单，只要将root-right-left依次放进栈中便可得到结果。
而后序遍历与前序遍历多了一个翻转的思想，入栈顺序为root-left-right，之后反转结果，便可得到后序遍历的结果。
最后是中序遍历，将所有左子树放入栈中，然后从左下角的节点开始出栈，每当出栈后，把节点值放入结果中，然后将右子树放入栈中，如此迭代，便可得到left-root-right的顺序。
