代码随想录算法训练营第十三天：树的认知（补五一）

‍

二叉树的递归遍历

#算法公开课

#思路

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

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> result;
        traversal(root, result);
        return result;
    }
};

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

二叉树的迭代遍历

#算法公开课

#思路

#前序遍历（迭代法）

class Solution {
public:
    vector<int> preorderTraversal (TreeNode* root){
        stack<TreeNode*> st;
        vector<int> result ;
        if (root == NULL)
            return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            result.push_back (node->val);
            if (root->right)st.push(root->right);
            if (root->left)st.push(root->left);
        }
        return result;
    }
};
上述超内存。下面代码可以通过
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val);
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            node = node->right;
        }
        return res;
    }
};

#中序遍历（迭代法）

class Solution{
public:
    vector<int> inorderTraversal(TreeNode* root){
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur != NULL || !st.empty()){
            if (cur != NULL){
                st.push(cur);
                cur = cur->left;
            }else {
                cur = st.top();
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }

        }
        return result;
    }
};

后序遍历（迭代法）

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

​​

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

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

#总结

Morris 中序遍历

思路与算法

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 O(1)O(1) O ( 1 ) 。

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 xxx）：

1. 如果 xxx 无左孩子，先将 xxx 的值加入答案数组，再访问 xxx 的右孩子，即 x=x.rightx = x.\textit{right} x = x . right。

2. 如果 xxx 有左孩子，则找到 xxx 左子树上最右的节点（即左子树中序遍历的最后一个节点， xxx 在中序遍历中的前驱节点），我们记为 predecessor\textit{predecessor} predecessor。根据 predecessor\textit{predecessor} predecessor 的右孩子是否为空，进行如下操作。

   • 如果 predecessor\textit{predecessor} predecessor 的右孩子为空，则将其右孩子指向 xxx，然后访问 xxx 的左孩子，即 x=x.leftx = x.\textit{left} x = x . left。
   • 如果 predecessor\textit{predecessor} predecessor 的右孩子不为空，则此时其右孩子指向 xxx，说明我们已经遍历完 xxx 的左子树，我们将 predecessor\textit{predecessor} predecessor 的右孩子置空，将 xxx 的值加入答案数组，然后访问 xxx 的右孩子，即 x=x.rightx = x.\textit{right} x = x . right。

其实整个过程我们就多做一步：假设当前遍历到的节点为 xxx，将 xxx 的左子树中最右边的节点的右孩子指向 xxx，这样在左子树遍历完成后我们通过这个指向走回了 xxx，且能通过这个指向知晓我们已经遍历完成了左子树，而不用再通过栈来维护，省去了栈的空间复杂度。

中序遍历演示：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
vector <int> res;
TreeNode *predecessor = nullptr;
while(root != nullptr){
    if (root->left!= nullptr){
        predecessor = root->left;
        while(predecessor->right!= nullptr && predecessor->right != root ){
            predecessor = predecessor->right;
        }
        if (predecessor->right == nullptr){
            predecessor->right = root;
            root = root->left;
        }
        else{
            res.push_back(root ->val);
            predecessor->right = nullptr;
            root = root->right;
        }
      
        }else{
            res.push_back(root->val);
            root = root->right;
    }
   
} return res;
    }
};

Morris遍历的详细解释+注释版

一些前置知识：

• 前驱节点，如果按照中序遍历访问树，访问的结果为ABC，则称A为B的前驱节点，B为C的前驱节点。
• 前驱节点pre是curr左子树的最右子树（按照中序遍历走一遍就知道了）。
• 由此可知，前驱节点的右子节点一定为空。

主要思想：

树的链接是单向的，从根节点出发，只有通往子节点的单向路程。

中序遍历迭代法的难点就在于，需要先访问当前节点的左子树，才能访问当前节点。

但是只有通往左子树的单向路程，而没有回程路，因此无法进行下去，除非用额外的数据结构记录下回程的路。

在这里可以利用当前节点的前驱节点，建立回程的路，也不需要消耗额外的空间。

根据前置知识的分析，当前节点的前驱节点的右子节点是为空的，因此可以用其保存回程的路。

但是要注意，这是建立在破坏了树的结构的基础上的，因此我们最后还有一步“消除链接”’的步骤，将树的结构还原。

重点过程： 当遍历到当前节点curr时，使用cuur的前驱节点pre

• 标记当前节点是否访问过
• 记录回溯到curr的路径（访问完pre以后，就应该访问curr了）

以下为我们访问curr节点需要做的事儿：

1. 访问curr的节点时候，先找其前驱节点pre
2. 找到前驱节点pre以后，我们根据其右指针的值，来判断curr的访问状态：

• pre的右子节点为空，说明curr第一次访问，其左子树还没有访问，此时我们应该将其指向curr，并访问curr的左子树
• pre的右子节点指向curr，那么说明这是第二次访问curr了，也就是说其左子树已经访问完了，此时将curr.val加入结果集中

后序遍历：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void addPath(vector<int> & vec,TreeNode *node){
        int count = 0;
        while(node!=nullptr){
            ++count;
            vec.emplace_back(node->val);
            node = node->right;
        }
        reverse(vec.end() - count,vec.end());
    }
    vector<int> postorderTraversal(TreeNode* root) {
vector<int>res;
if (root == nullptr){
    return res;
}
TreeNode *p1 = root,*p2= =nullptr;
while(p1 != nullptr){
    p2 = p1->left;
    if(p2 != nullptr){
        while(p2->right != nullptr && p2->right != p1)
        {
            p2 = p2 -> right;
        }
        if (p2 ->right ==nullptr){
            p2 ->right = p1;
            p1 = p1->left;
            continue;
        }
        else{
            p2->right = nullptr;
            addPath(res,p1->left);
        }
    }
    p1 = p1->right;
}
addPath(res,root);
return res;
    }
};

下面是上述代码的详细注释和解释。这段代码实现了对二叉树的后序遍历（left-right-root）算法。 一般后序遍历有递归和迭代两种实现方法，这个解决方案使用了迭代方式，并利用了Morris遍历算法的思想，该算法用以减少空间复杂度至O(1)，通过修改树的结构来记录访问路径。具体到这份代码，它实现了一种特殊方式的后序遍历。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 将从当前节点到最右子节点的路径逆序加入到结果数组中
    void addPath(vector<int> & vec,TreeNode *node){
        int count = 0;
        while(node != nullptr){
            ++count; // 记录路径长度，以便逆序
            vec.emplace_back(node->val); // 加入当前节点值
            node = node->right; // 移动到右子节点
        }
        reverse(vec.end() - count,vec.end()); // 将刚刚记录的路径逆序
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        if (root == nullptr){ // 如果根节点是空，则直接返回空结果
            return res;
        }

        TreeNode *p1 = root,*p2 = nullptr;
        while(p1 != nullptr){
            p2 = p1->left;
            if(p2 != nullptr){
                // 寻找左子树中的最右节点，即当前p1子树的前驱
                while(p2->right != nullptr && p2->right != p1){
                    p2 = p2 -> right;
                }
                if (p2 ->right == nullptr){
                    // 建立临时的指向p1的链接，方便后面返回到p1并访问右子树
                    p2 ->right = p1;
                    p1 = p1->left; // 继续遍历左子树
                    continue;
                }
                else{
                    // 如果前驱的right已经指向了p1，说明左子树已经访问完，需要断开链接
                    p2->right = nullptr;
                    // 将从当前节点到最右子节点的路径逆序加入到结果数组中
                    addPath(res,p1->left);
                }
            }
            p1 = p1->right; // 访问右子树
        }
        // 由于根节点最后被访问，所以在最后将从根节点开始的直到最右节点的路径逆序加入。
        addPath(res,root);
        return res;
    }
};

这段代码通过定义addPath​函数来实现将一段路径逆序加入结果数组中。此函数的关键应用是在遍历到左子树的最右侧时，可以按后序遍历的要求实际上逆序地处理节点（因为原本是直接通过right​指针向右访问，但逆序后实际上形成了从底部向上访问左子树的每个节点的效果，符合后序遍历的访问顺序）。整体算法在处理每个左子节点的时候，尝试找到它的前驱节点，如果未被访问，则建立一条临时的回溯链接，一旦找到或重新访问到，就删除这条链接，使用addPath​函数逆序地加入这部分节点的值到结果中，最后处理右子节点。整个过程中不使用递归或栈，而是通过修改原树结构来达到访问的目的，最终还原树的结构。 这种方法特别之处在于它利用了树的结构作为遍历过程中的“栈”，通过修改节点的right指针来进行遍历的回溯，从而实现了空间复杂度为O(1)的后序遍历。这是一种非常巧妙且效率高的遍历方式，特别适用于要求低空间复杂度的场景。

二叉树的统一迭代法

#思路

迭代法中序遍历

中序遍历代码如下：（详细注释）

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();
                result.push_back(node->val); // 加入到结果集
            }
        }
        return result;
    }
};

看代码有点抽象我们来看一下动画(中序遍历)：

​​

动画中，result数组就是最终结果集。

可以看出我们将访问的节点直接加入到栈中，但如果是处理的节点则后面放入一个空节点， 这样只有空节点弹出的时候，才将下一个节点放进结果集。

此时我们再来看前序遍历代码。

#迭代法前序遍历

class Solution {
public:
    vector<int> preorderTraversal(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);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

#迭代法后序遍历

class Solution {
public:
    vector<int> postorderTraversal(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();
                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();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

#总结