代码随想录算法训练营 DAY 14 | 二叉树的递归遍历和迭代遍历

二叉树基础

种类

满二叉树：深度为k，有2^k-1个节点的二叉树

完全二叉树：除了最底层可能没满，且都在靠左侧

• 优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树：二叉搜索树是一个有序树

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

平衡二叉搜索树（AVL树）：一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

• java容器中的二叉树：

TreeSet集合是基于TreeMap的实现，而TreeMap是基于二叉树（红黑树）结构，也就是说TreeSet集合的底层使用的二叉树（红黑树）结构。

存储方式

• 链式存储

• 顺序存储
  

数组存储二叉树的遍历：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

遍历方式

有两种遍历方式：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
   • 前序遍历（递归法，迭代法）
   • 中序遍历（递归法，迭代法）
   • 后序遍历（递归法，迭代法）
2. 广度优先遍历：一层一层的去遍历。
   • 层次遍历（迭代法）

前中后，其实指的就是中间节点的遍历顺序。左和右指的是左子树和右子树！

• 前序遍历：中左右
• 中序遍历：左中右
• 后序遍历：左右中

栈其实就是递归的一种实现结构，前中后序遍历的逻辑其实都可以借助栈使用递归的方式来实现的。

广度优先遍历的实现一般使用队列来实现。

java定义方式

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二叉树的递归遍历

视频链接：https://www.bilibili.com/video/BV1Wh411S7xt/?vd_source=80cf8293f27c076730af6c32ceeb2689

讲解连接：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

对应题目：

144.二叉树的前序遍历

145.二叉树的后序遍历

94.二叉树的中序遍历

这类问题一般都是传入一个根节点，要求返回一个存放遍历顺序的list。

核心思路

递归问题按照三步走：

• 确定递归函数的参数和返回值
• 确定终止条件
• 确定单层递归的逻辑

前序遍历

1. 确定递归函数的参数和返回值

   递归函数：void traversal(cur, list)

2. 确定终止条件

   什么时候终止遍历开始返回？遇到null

   if(cur==null) return;

3. 确定单层递归的逻辑

   中：list.add(cur)

   左：traversal(cur.left, list)

   右：traversal(cur.right, list)

• java代码

//144.前序遍历
class Solution {
    void transfer (TreeNode cur, List<Integer> res) {
        if(cur == null) return;
        res.add(cur.val);
        transfer(cur.left, res);
        transfer(cur.right, res);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        transfer(root, res);
        return res;
    }
}

//145.后序遍历
class Solution {
    void transfer (TreeNode cur, List<Integer> res) {
        if(cur == null) return;
        transfer(cur.left, res);
        transfer(cur.right, res);
        res.add(cur.val);
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        transfer(root, res);
        return res;
    }
}

//94.中序遍历
class Solution {
    void transfer (TreeNode cur, List<Integer> res) {
            if(cur == null) return;
            transfer(cur.left, res);
            res.add(cur.val);
            transfer(cur.right, res);
        }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        transfer(root, res);
        return res;
    }
}
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
45
46
47

迭代遍历

我们用栈来模拟迭代遍历。

一共分为两步操作：访问节点+处理节点

前序

前序：中 左 右

注意空节点不入栈！

首先我们把5入栈。然后把5弹出，放进数组里。

然后把6 4入栈。为什么按照右 左的顺序入栈？–因为栈先进后出，要保证出栈的顺序是左 右！

然后把4弹出，（把4当做中）再处理4的左和右：把2 1入栈。然后弹出1，弹出2，弹出6。

• java代码

 //前序：中左右 入栈顺序：中右左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        if(root == null) return res;
        st.push(root);  //先把根节点放进去
        while(!st.empty()) {  //一次循环就是一次中左右的处理
            TreeNode node = st.peek();  //保存一下栈顶元素（中）
            st.pop();  //先把中 出栈
            res.add(node.val);
            if (node.right != null){
                st.push(node.right);
            }
            if (node.left != null){
                st.push(node.left);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

后序

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

• java代码

 //前序中左右--反转左右--变成中右左---整个res反转--左右中（后序）
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        if(root == null) return res;
        st.push(root);  //先把根节点放进去
        while(!st.empty()) {  //一次循环就是一次中左右的处理
            TreeNode node = st.peek();  //保存一下栈顶元素（中）
            st.pop();  //先把中 出栈
            res.add(node.val);
            if (node.left != null){
                st.push(node.left);
            }
            if (node.right != null){
                st.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

中序

中序是左中右，先访问中，但是要先处理的是左。这就造成了访问顺序和处理顺序不一样！

那怎么办？

我们需要一个指针cur帮助我们遍历二叉树，处理的时候把元素加入到res数组里。

要用栈来记录我们遍历过的顺序。因为在处理元素的时候其实是按遍历的顺序逆向输出的！

非空就入栈，指针往左走，当前为空了就出栈 同时输出到数组 往右走！

• 遍历终止条件：while(cur==null || stk.empty())

右孩子不为空,此时右孩子的这个点就当作根节点一样处理,是一棵新树,然后右孩子要入栈,接着像最开始一样继续找左,这个是迭代循环的关键

• java代码

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;  //cur从根节点开始
        while (cur != null || !stack.isEmpty()){  //循环终止条件
           if (cur != null){  //如果cur为空就入栈，同时往左
               stack.push(cur);
               cur = cur.left;
           }else{  //cur不为空就出栈一个 同时令cur=出栈的 把val加入数组 同时往右遍历（把它当作根 开始新一轮）
               cur = stack.pop();  
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

统一迭代法

中序遍历里，使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

迭代法中序遍历

//中
st.push(node);               
st.push(null);

//右
if (node.right!=null) st.push(node.right);  
    
//左
if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
1
2
3
4
5
6
7
8
9

• 中序遍历Java代码 右中左

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}
        return result;
    }
}
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
45
46
47

• 前序遍历 右左中

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右左中节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 后序遍历 中右左

class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将中右左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）     
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

day14总结

• 翻转数组：Collections.reverse(传一个list)

• 递归遍历按照三步走：

  • 确定递归函数的参数和返回值
  • 确定终止条件
  • 确定单层递归的逻辑

• 迭代遍历，先看前序。用栈来模拟迭代遍历。

  一共分为两步操作：访问节点+处理节点

  前序：中 左 右。但是按照右-左顺序入栈

  后序就是交换左右顺序，然后整个res反转。

• 迭代遍历中序：需要一个指针cur帮助我们遍历二叉树，处理的时候把元素加入到res数组里。

  非空就入栈，指针往左走，当前为空了就出栈 同时输出到数组 往右走！