非递归实现二叉树的前序、中序、后序遍历-创新互联

目录

非递归实现二叉树的前序遍历 

非递归实现二叉树的中序遍历

非递归实现二叉树的后序遍历

根据二叉树的前序和中序遍历结果还原二叉树 

根据二叉树的中序和后序遍历结果还原二叉树

非递归遍历需要借助栈。 

前序遍历：二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。

1. 如果树为空，直接返回

2. 如果树非空：从根节点位置开始遍历，因为前序遍历规则：根节点、左子树、右子树

a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈，并访问。

  b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点，其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍历，继续a步骤

vectorpreorderTraversal(TreeNode* root) {
        vectorv;
        stackst;
        TreeNode*cur = root;
        while(cur || !st.empty())
        {
            //循环每走一次迭代，就是在访问一棵树的开始

            //访问左路节点，左路节点入栈
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }

            //取出节点，访问右路节点
            TreeNode* top = st.top();
            st.pop();

            //子问题形式访问右子树
            cur = top->right;
        }
        return v;
    }

中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

中序遍历中，从栈中弹出的节点，其左子树是访问完了，可以直接访问该节点，然后接下来访问右子树。

1. 如果树为空，直接返回

2. 如果树非空：从根节点位置开始遍历，因为前序遍历规则：左子树、根节点、右子树

a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈，并访问。

  b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，可以直接遍历该节点，对于该节点，其左子树已经遍历，该节点也已经遍历，剩余其右子树没有遍历，将其左子树当成一棵新的树开始遍历，继续a步骤

vectorinorderTraversal(TreeNode* root) {
        vectorv;
        stackst;
        TreeNode*cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();

            v.push_back(top->val);

            cur = top->right;
        }
        return v;
    }

后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。

后序遍历中，从栈中弹出的节点，我们只能确定其左子树肯定访问完了，但是无法确定右子树是否访问过。因此，我们在后序遍历中，引入了一个prev来记录历史访问记录。

1. 如果树为空，直接返回

2. 如果树非空：从根节点位置开始遍历，但此时根节点不能遍历，因为后序遍历规则：左子树、右子树、根节点

     a. 沿着根节点一直往左走，将所经过路径中的节点依次入栈

     b. 取栈顶元素，该元素取到后，其左子树要么为空，要么已经遍历，但是此时该节点不能遍历，除非其右子树不存在或者其右子树已经遍历，才可以遍历该节点，如果该节点右子树没有遍历，将其右子树作为一棵新的二叉树遍历，继续a

• 当访问完一棵子树的时候，我们用prev指向该节点。
• 这样，在回溯到父节点的时候，我们可以依据prev是指向左子节点，还是右子节点，来判断父节点的访问情况。
  

vectorpostorderTraversal(TreeNode* root) {
        vectorv;
        stackst;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            //现在需要确定的是是否有右子树，或者右子树是否访问过
            //如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时
            //说明可以访问当前节点
            if(top->right == nullptr || top->right == prev)
            {
                v.push_back(top->val);
                //更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
                prev = top;
                st.pop();
            }
            else
            {
                //右子树没有访问过，访问右子树
                cur = top->right;
            }
            
        }
        return v;
    }

1. 从前序遍历结果中获取到树的根节点

2. 在中序遍历结果中确定根节点的位置，按照该位置将中序遍历结果分为两部分

左半部分是根节点的左子树，递归创建根节点的左子树

右半部分是根节点的右子树，递归创建根节点的右子树

TreeNode* _buildTree(vector& preorder, vector& inorder,int& previ,int inbegin,int inend) {
        if(inbegin >inend)
            return NULL;
        TreeNode* root = new TreeNode(preorder[previ]);
        int rooti = inbegin;
        while(rooti<= inend)
        {
            if(inorder[rooti] == preorder[previ])
                break;
            else
                ++rooti;
                
        }
        ++previ;
        //[inbegin rooti-1] rooti [rooti+1,inend]
        root->left = _buildTree(preorder,inorder,previ,inbegin,rooti-1);
        root->right = _buildTree(preorder,inorder,previ,rooti+1,inend);
        return root;
    }
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        int previ = 0;
       return  _buildTree(preorder,inorder,previ,0,inorder.size()-1);
    }

1. 从后序遍历结果中获取到树的根节点，注意：后序遍历规则：左子树、右子树、根节点，因此应该从后往前获取根节点

2. 在中序遍历结果中确定根节点的位置，按照该位置将中序遍历结果分为两部分

右半部分是根节点的右子树，递归创建根节点的右子树---->注意先要还原根的右子树

左半部分是根节点的左子树，递归创建根节点的左子树

TreeNode* _buildTree(vector& inorder, vector& postorder,int& posti,int inbegin,int inend) {
        if(inbegin >inend)
            return NULL;
        TreeNode* root = new TreeNode(postorder[posti]);
        int rooti = inbegin;
        while(rooti<= inend)
        {
            if(postorder[posti] == inorder[rooti])
                break;
            else
                ++rooti;
        }
        --posti;
        root->right = _buildTree(inorder,postorder,posti,rooti+1,inend);
        root->left = _buildTree(inorder,postorder,posti,inbegin,rooti-1);
        
        return root;
    }
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        int posti = postorder.size()-1;
        return _buildTree(inorder,postorder,posti,0,inorder.size()-1);
    }

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧