代码随想录算法训练营day14 | 二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代

今天开始二叉树的学习。

关于二叉树的理论基础，可以参考：

链接: 二叉树理论基础

二叉树的递归遍历

写递归的思路

每次写递归，按照这个步骤来写：

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

拿下面三题来练手：

二叉树的前序遍历

链接: 二叉树的前序遍历

1. 确定递归函数的参数和返回值：
   因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void

void traversal(TreeNode* cur, vector<int>& vec)
1

2. 确定终止条件：
   在递归的过程中，当前遍历的结点是空的，那么本层递归就要结束了，所以如果当前遍历的这个结点是空，就直接return。

if (cur == NULL) return;
1

3. 确定单层递归的逻辑：
   前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值

vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右
1
2
3

最终代码：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) 
        	return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> re;
        traversal(root, res);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉树的中序遍历

链接: 二叉树的中序遍历
跟前序遍历大差不差，更改下位置即可，后序遍历也是一样的道理

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == nullptr)
            return;
        traversal(cur->left, vec);  //左
        vec.push_back(cur->val);    //中
        traversal(cur->right, vec); //右
        
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root,res);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树的后序遍历

链接: 二叉树的后序遍历

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == nullptr)
            return;
 		traversal(cur->left, vec);  // 左
    	traversal(cur->right, vec); // 右
    	vec.push_back(cur->val);    // 中
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root, res);
        return res;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二叉树的迭代遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，所以可以使用栈，即非递归的方式来没实现二叉树的前中后序遍历。

二叉树的前序遍历

• 处理：将元素放进res数组中
• 访问：遍历节点

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

这样的顺序因为这样出栈的时候才是中左右的顺序。
注：代码中空结点不入栈

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == NULL) return res;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();                       // 中
            st.pop();
            res.push_back(node->val);
            if (node->right) st.push(node->right);           // 右（空结点不入栈）
            if (node->left) st.push(node->left);             // 左（空结点不入栈）
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二叉树的中序遍历

此时不是想改一点前序遍历代码顺序就把中序遍历搞出来。

前序遍历的顺序是中左右，先访问的元素是中间结点，要处理的元素也是中间结点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间结点。

中序遍历是左中右，先访问的是二叉树顶部的结点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理结点(也就是在把节点的数值放进res数组中)，这就造成了处理顺序和访问顺序是不一致的。

在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问结点，栈则用来处理节点上的元素

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问结点，访问到最底层
                st.push(cur); // 将访问的结点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进res数组里的数据）
                st.pop();
                res.push_back(cur->val);     // 中
                cur = cur->right;               // 右
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二叉树的后序遍历

后序遍历是左右中，只需要调整一下前序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转res数组，输出的结果顺序就是左右中了。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空结点不入栈）
            if (node->right) st.push(node->right); // 空结点不入栈
        }
        reverse(res.begin(), res.end()); // 将结果反转之后就是左右中的顺序了
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树的统一迭代

将二叉树前后中序遍历的迭代法实现风格统一（即前序遍历 改变代码顺序就可以实现中序 和 后序）

迭代法实现的前中后序，风格也不是那么统一，除了前序和后序有关联，中序完全就是另一个风格，一会用栈遍历，一会又用指针来遍历。

在刚刚迭代法遍历的讲解说了，使用栈的话，无法同时解决访问节点（遍历结点）和处理结点（将元素放进结果数组）不一致的情况。

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

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

二叉树的中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左结点添加到栈中
                if (node->right) st.push(node->right);  // 添加右结点（空节点不入栈）

                st.push(node);                          // 添加中结点
                st.push(NULL); // 中结点访问过，但是还没有处理，加入空结点做为标记。

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

二叉树的前序遍历

和中序遍历相比仅仅改变了两行代码的顺序

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        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

二叉树的后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                st.push(node);                          // 中
                st.push(NULL);

                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                res.push_back(node->val);
            }
        }
        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

总结

使用其中一种方法即可，个人认为递归法最容易理解且代码量少。
迭代法太麻烦了，光理解就花了我不少时间，更别说实现代码了。。。

• 参考文档：
  链接: 二叉树的递归遍历
  链接: 二叉树的迭代遍历
  链接: 二叉树的统一迭代