Leetcode: Binary Tree Postorder Traversal（二叉树后序遍历）

迈不过友情╰ 2022-08-07 11:40 5阅读 0赞

题目：  
Given a binary tree, return the postorder traversal of its nodes’ values.

For example:  
Given binary tree \{1,\#,2,3\},

1
        \
         2
        /
       3

return \[3,2,1\].

Note: Recursive solution is trivial, could you do it iteratively?

递归解法（C++版本）：

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution
    {
    private:
        vector<int> result;
    public:
        vector<int> postorderTraversal(TreeNode *root)
        {
            if (root)
            {
                postorderTraversal(root->left);
                postorderTraversal(root->right);
                result.push_back(root->val);
            }
            return result;
        }
    };

**二叉树非递归后序遍历思路：**  
二叉树非递归后续遍历是三种遍历中最难的，因为后续遍历最后访问根节点，操作中不好回溯到根节点，而前序遍历和中序遍历中，每次循环遍历中都是从根节点开始回溯很容易。  
网上好些代码都是使用一个栈Stack进行操作的，代码不易懂，读起来很吃力。  
其实，可以使用两个Stack来进行二叉树非递归后续遍历。先访问根节点，入栈（A栈），记住根节点，出栈进入另外一个栈（B栈），然后该根节点左右子树入栈（A栈）。最后输出B栈的结果就OK了。

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution
    {
    public:
        vector<int> postorderTraversal(TreeNode *root)
        {
            vector<int> result;
            if (!root) return result;
            stack<TreeNode*> outputStack;
            stack<TreeNode*> middleStack;
            middleStack.push(root);
            TreeNode *node = nullptr;
            while (!middleStack.empty())
            {
                node = middleStack.top();
                middleStack.pop();
                outputStack.push(node);
                if (node->left)
                {
                    middleStack.push(node->left);
                }
                if (node->right)
                {
                    middleStack.push(node->right);
                }
            }
            while (!outputStack.empty())
            {
                result.push_back(outputStack.top()->val);
                outputStack.pop();
            }
            return result;
        }
    };

C\#非递归参考代码：

/** * Definition for binary tree * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */
    public class Solution { 
        public IList<int> PostorderTraversal(TreeNode root)
        {
            IList<int> result = new List<int>();
            if (root == null) return result;
            Stack<TreeNode> outputStack = new Stack<TreeNode>();
            Stack<TreeNode> middleStack = new Stack<TreeNode>();
            middleStack.Push(root);
            TreeNode node = null;
            while (middleStack.Count != 0)
            {
                node = middleStack.Pop();
                outputStack.Push(node);
                if (node.left != null) middleStack.Push(node.left);
                if (node.right != null) middleStack.Push(node.right);
            }
            while (outputStack.Count != 0)
            {
                result.Add(outputStack.Pop().val);
            }
            return result;
        }
    }