二叉树的遍历

以 1 二叉树为例讲解：

​ 2 3

4 5 6 7

递归法

思路：

按照递归调用的机制，我们按照只要遍历到就打印的方式得到的数据为：

​ 【1，2，4，4，4，2，5，5，5，2，1，3，6，6，6，3，7，7，7，3，1】

前序遍历

​ 我们将前序遍历所得到的数据都是在调用递归机制的元素首次出现的位置，那么按照前序遍历：【中 - 左 - 右】的顺序即可完成

所以我们得到的就是【1，2，4，5，3，6，7，1】

1
2
3
4
5
6
7
8
9
10
public void prefix(){
    System.out.println(this);

    if(this.left != null){
        this.left.prefix();
    }
    if (this.right != null){
        this.right.prefix();
    }
}

中序遍历

​ 中序遍历所得到的数据都是在调用递归机制的元素第二次出现的位置，那么按照前序遍历：【左 - 中 - 右】的顺序即可完成

所以我们得到的就是【4，2，5，1，6，3，7】

1
2
3
4
5
6
7
8
9
10
11
//中序遍历
public void infix(){
    if(this.left != null){
        this.left.infix();
    }
    System.out.println(this);

    if (this.right != null){
        this.right.infix();
    }
}

后序遍历

​ 后序遍历所得到的数据都是在调用递归机制的元素最后一次出现的位置，那么按照前序遍历：【左 - 右 - 中】的顺序即可完成

所以我们得到的就是【4，5，2，6，7，3，1】

1
2
3
4
5
6
7
8
9
10
11
12
//后序遍历
public void suffix(){
    if(this.left != null){
        this.left.suffix();
    }

    if (this.right != null){
        this.right.suffix();
    }

    System.out.println(this);
}

​

迭代法

思路：

​ 首先我们来了解一下递归的实现： 每一次递归调用都会把函数的局部变量、参数和返回值等都压入调用栈，然后在结束本层递归操作的时候，从栈顶弹出上一次递归的各项参数，这也是为什么递归可以返回上一层位置的原因。

​ 那么由此我们也可以不用递归，知道了递归调用的本质实现方法，我们就可以自己用栈实现。

前序遍历

​ **思路 ： **

​ 前序遍历是 【中 -> 左 -> 右】那么我们就可以从根节点加入栈，然后将右孩子 加入栈 最后再将左孩子 压入栈 ，这样我们得到的出栈顺序就是 【中 -> 左 -> 右】

  1. 将root根节点压入栈
  2. 进入循环，出栈
  3. 打印出栈节点的val
  4. 判断右孩子是否为null ，如果不是，将右孩子压入栈
  5. 判断左孩子是否为null， 如果不是，将左孩子压入栈
  6. 循环【3->5】当栈为空时 退出循环，得到结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return list;
    }

}

中序遍历

**思路： **

​ 中序遍历和前序遍历有所不同，中序遍历的顺序是【中- > 左 - > 右 】。

  1. 先将所有左边的节点全部入栈，直到left== null为止，否则一直顺序的进栈
  2. 当left为null时，出栈 ，然后将出栈的出栈的节点的val打印
  3. 将节点右移
  4. 当【temp(临时节点) 为空， 并且栈也为空时】退出循环， 否则继续【1- > 3】步骤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null){
            return list;
        }
        Stack<TreeNode> s = new Stack<>();
        TreeNode node = root;
        while(node != null || !s.isEmpty()){
            if(node != null){
                s.push(node);
                node = node.left;
            }else{
                node = s.pop();
                list.add(node.val);
                node = node.right;
            }
        }
        return list;
    }
}

后序遍历

后序遍历的顺序是【左 -> 右 -> 中】，与前两者不同，我们需要两个栈 ，栈s1 和 s2

其实经过第一轮的入栈出栈之后，得到的结果就是后序遍历结果的反转数，所以再次入栈出栈后我们就可以得到后序遍历的完整结果

  1. 先将根节点压入栈，然后进入循环
  2. 进入循环后先将栈s1 中的元素出栈，并入s2栈
  3. 判断左孩子是否为null ，如果不是，将左孩子压入栈s1
  4. 判断右孩子是否为null， 如果不是，将右孩子压入栈s1
  5. 【当栈s1为空时】退出循环，否则继续【2- > 4】
  6. 将栈s2顺序出栈，并打印
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
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null){
            return list;
        }

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        TreeNode node = root;
        s1.push(node);
        while(!s1.isEmpty()){
            node = s1.pop();
            s2.push(node);
            if(node.left != null){
                s1.push(node.left);
            }
            if(node.right != null){
                s1.push(node.right);
            }
        }
        while(!s2.isEmpty()){
            TreeNode cur = s2.pop();
            list.add(cur.val);
        }
        return list;
    }
}