基础知识

递归遍历

解题思路

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);   //右
    }
};

迭代遍历

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

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

前序

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

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

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

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

 中序

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

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

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

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

 统一迭代法

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

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

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

 

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

收获

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

05-12 04:24