代码随想录算法训练营第十四天 | 二叉树基础知识、递归遍历、迭代遍历、统一迭代

基础知识

递归遍历

解题思路

1.确定要传入的参数和返回值

2.注意终止条件 

3.确定单层递归的逻辑

中序和后序按照中左右，左右中的顺序即可

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
             vector<int> result;
             traverSal(root,result);
             return result;
    }

    void traverSal(TreeNode* node, vector<int>& vec)
    {
        if(node==nullptr) return;    //终止条件
        vec.push_back(node->val);    //将节点值压入栈，中
        traverSal(node->left,vec);   //左
        traverSal(node->right,vec);   //右
    }
};

迭代遍历

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因

因此可以用栈来模拟递归。

前序

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

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序

 

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root ==nullptr) return result;   //剪枝
        st.push(root);    //压入根节点
        while(!st.empty())   //当栈不为空时
        {
             TreeNode* node = st.top();   //中
             st.pop();  
             result.push_back(node->val);
             if(node->right) st.push(node->right);  //右，空节点不如栈 
             if(node->left)  st.push(node->left);   //左，空节点不入栈
        }
        return result;
    }
};

后序

只需要将中右左换为中左右，那么出栈就会变成中右左，最后再对数组倒序输出一下，就是左右中的顺序

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root ==nullptr) 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);  //右，空节点不如栈 
        }
        for(int i=0,j=result.size()-1;i<=j;i++,j--)
        {
             swap(result[i],result[j]);
        }
        return result;
    }
};

 中序

中序遍历和前后序并不相同，因为遍历顺序和处理顺序并不一样，因此不一样。需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。栈用于记录自己访问过的元素。

 思路：自己节点不为空，则压入栈，当自己为空后（一旦没有左孩子，自己就为中节点），记录并弹出栈顶元素（这是我们最近访问过的左节点，那么按照上述说的，我们还要去看右孩子）， 如果右孩子为空则继续弹出（代表这一个子树遍历完成了），如果右孩子不为空，则继续入栈。

 

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur!=nullptr || !st.empty())
        {
            if(cur!=nullptr)
            {
                st.push(cur);   //如果左孩子不为空，则自己为中节点，压入栈，并移动指针到左孩子，一直到最底层
                cur = cur->left;
            }
            else
            {
                //如果此时作为右空节点，那么就会回到作为左节点的子树的中节点
                cur = st.top();
                st.pop();
                result.push_back(cur->val);     //如果左孩子为空，则自己就是中节点了，弹出到结果，再去判断右节点
                cur = cur->right;
            }

        }
        return result;
    }
};

 统一迭代法

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

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

 

 

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;
    }
};

收获

统一迭代没想明白，之后再回来看看