二叉树的后序遍历（迭代法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的后序遍历（迭代法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1751字，纯文字阅读大概需要3分钟。

内容图文

 

 迭代法说白了就是用栈模拟了递归解法的过程，先上代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return list()
        
        res = list()
        stack = list()
        prev = None

        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()     #1
            if not root.right or root.right == prev:
                res.append(root.val)
                prev = root
                root = None　　　　#2
            else:
                stack.append(root)
                root = root.right   #3
        
        return res

 

到#1为止，可以看到stack将根节点和每个访问的节点的左节点都入栈了，之后将最深最左侧的节点，也就是后序遍历的第一个节点弹出（这个节点已经没有左节点了）。

#2 节点如果没有右节点（就是它是左侧一支）那么就可以把他加到结果里了，同时记录这个点，并将root置空

#3 节点有右节点说明这个是根节点，那么继续将根节点入栈（先进后出嘛），然后root指向那个右节点，第一轮完事。

第二轮：root成为了None  或者 上一次加入栈节点的右节点，None的话就从栈里pop出来一个给它，说明这个是根节点，如果是右节点，先给它入栈（因为马上出栈的也是它只是要先找找它的左侧节点）那么继续找这个节点的左侧节点，没有的话说明这个也是个根节点，和None相同。

 leetcode上大神还有用c++写出了比较好看的后续遍历

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

作者：carlsun-2

　　

内容总结

以上是互联网集市为您收集整理的二叉树的后序遍历（迭代法）全部内容，希望文章能够帮你解决二叉树的后序遍历（迭代法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---