Binary Tree Postorder Traversal

Tags: Tree, Stack, Hard

Question

Problem Statement

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

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

  1.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [3,2,1].

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

题解1 - 递归

首先使用递归便于理解。

Python - Divide and Conquer

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     # @param {TreeNode} root
  10.     # @return {integer[]}
  11.     def postorderTraversal(self, root):
  12.         if root is None:
  13.             return []
  14.         else:
  15.             return self.postorderTraversal(root.left) +\
  16.                    self.postorderTraversal(root.right) + [root.val]

C++ - Traversal

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14.     /**
  15.      * @param root: The root of binary tree.
  16.      * @return: Postorder in vector which contains node values.
  17.      */
  18. public:
  19.     vector<int> postorderTraversal(TreeNode *root) {
  20.         vector<int> result;
  22.         traverse(root, result);
  24.         return result;
  25.     }
  27. private:
  28.     void traverse(TreeNode *root, vector<int> &ret) {
  29.         if (root == NULL) {
  30.             return;
  31.         }
  33.         traverse(root->left, ret);
  34.         traverse(root->right, ret);
  35.         ret.push_back(root->val);
  36.     }
  37. };

Java - Divide and Conquer

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public List<Integer> postorderTraversal(TreeNode root) {
  12.         List<Integer> result = new ArrayList<Integer>();
  13.         if (root != null) {
  14.             List<Integer> left = postorderTraversal(root.left);
  15.             result.addAll(left);
  16.             List<Integer> right = postorderTraversal(root.right);
  17.             result.addAll(right);
  18.             result.add(root.val);
  19.         }
  21.         return result;
  22.     }
  23. }

Java - Traversal

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     private List<Integer> result = new ArrayList<Integer>();
  13.     public List<Integer> postorderTraversal(TreeNode root) {
  14.         if (root != null) {
  15.             postorderTraversal(root.left);
  16.             postorderTraversal(root.right);
  17.             result.add(root.val);
  18.         }
  19.         return result;
  20.     }
  21. }

源码分析

递归版的太简单了，没啥好说的，注意入栈顺序。

复杂度分析

时间复杂度近似为 O(n).

题解2 - 迭代

使用递归写后序遍历那是相当的简单，我们来个不使用递归的迭代版。整体思路仍然为「左右根」，那么怎么才能知道什么时候该访问根节点呢？问题即转化为如何保证左右子节点一定先被访问到？由于入栈之后左右节点已无法区分，因此需要区分左右子节点是否被访问过(加入到最终返回结果中)。除了有左右节点的情况，根节点也可能没有任何子节点，此时也可直接将其值加入到最终返回结果中。

Python

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     # @param {TreeNode} root
  10.     # @return {integer[]}
  11.     def postorderTraversal(self, root):
  12.         result = []
  13.         if root is None:
  14.             return result
  15.         s = []
  16.         # previously traversed node
  17.         prev = None
  18.         s.append(root)
  19.         while s:
  20.             curr = s[-1]
  21.             noChild = curr.left is None and curr.right is None
  22.             childVisited = (prev is not None) and \
  23.                            (curr.left == prev or curr.right == prev)
  24.             if noChild or childVisited:
  25.                 result.append(curr.val)
  26.                 s.pop()
  27.                 prev = curr
  28.             else:
  29.                 if curr.right is not None:
  30.                     s.append(curr.right)
  31.                 if curr.left is not None:
  32.                     s.append(curr.left)
  34.         return result

C++

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     vector<int> postorderTraversal(TreeNode* root) {
  13.         vector<int> result;
  14.         if (root == NULL) return result;
  16.         TreeNode *prev = NULL;
  17.         stack<TreeNode *> s;
  18.         s.push(root);
  19.         while (!s.empty()) {
  20.             TreeNode *curr = s.top();
  21.             bool noChild = false;
  22.             if (curr->left == NULL && curr->right == NULL) {
  23.                 noChild = true;
  24.             }
  25.             bool childVisited = false;
  26.             if (prev != NULL && (curr->left == prev || curr->right == prev)) {
  27.                 childVisited = true;
  28.             }
  30.             // traverse
  31.             if (noChild || childVisited) {
  32.                 result.push_back(curr->val);
  33.                 s.pop();
  34.                 prev = curr;
  35.             } else {
  36.                 if (curr->right != NULL) s.push(curr->right);
  37.                 if (curr->left != NULL) s.push(curr->left);
  38.             }
  39.         }
  41.         return result;
  42.     }
  43. };

Java

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public List<Integer> postorderTraversal(TreeNode root) {
  12.         List<Integer> result = new ArrayList<Integer>();
  13.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  15.         if (root != null) stack.push(root);
  16.         TreeNode prev = null;
  17.         while (!stack.isEmpty()) {
  18.             TreeNode curr = stack.peek();
  19.             boolean noChild = (curr.left == null && curr.right == null);
  20.             boolean childVisited = false;
  21.             if (prev != null && (curr.left == prev || curr.right == prev)) {
  22.                 childVisited = true;
  23.             }
  24.             if (noChild || childVisited) {
  25.                 curr = stack.pop();
  26.                 result.add(curr.val);
  27.                 prev = curr;
  28.             } else {
  29.                 if (curr.right != null) stack.push(curr.right);
  30.                 if (curr.left != null) stack.push(curr.left);
  31.             }
  32.         }
  34.         return result;
  35.     }
  36. }

源码分析

遍历顺序为『左右根』，判断根节点是否应该从栈中剔除有两种条件，一为无子节点，二为子节点已遍历过。判断子节点是否遍历过需要排除prev == null 的情况，因为 prev 初始化为 null. Java 中在 while 内部新建 curr 变量而不是复用 root 有一定性能提升，不知是不是 JVM 运行时优化导致的。

将递归写成迭代的难点在于如何在迭代中体现递归本质及边界条件的确立，可使用简单示例和纸上画出栈调用图辅助分析。

复杂度分析

最坏情况下栈内存储所有节点，空间复杂度近似为 O(n), 每个节点遍历两次或以上，时间复杂度近似为 O(n).

题解3 - 反转先序遍历

要想得到『左右根』的后序遍历结果，我们发现只需将『根右左』的结果转置即可，而先序遍历通常为『根左右』，故改变『左右』的顺序即可，所以如此一来后序遍历的非递归实现起来就非常简单了。

C++

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14.     /**
  15.      * @param root: The root of binary tree.
  16.      * @return: Postorder in vector which contains node values.
  17.      */
  18. public:
  19.     vector<int> postorderTraversal(TreeNode *root) {
  20.         vector<int> result;
  21.         if (root == NULL) return result;
  23.         stack<TreeNode*> s;
  24.         s.push(root);
  25.         while (!s.empty()) {
  26.             TreeNode *node = s.top();
  27.             s.pop();
  28.             result.push_back(node->val);
  29.             // root, right, left => left, right, root
  30.             if (node->left != NULL) s.push(node->left);
  31.             if (node->right != NULL) s.push(node->right);
  32.         }
  33.         // reverse
  34.         std::reverse(result.begin(), result.end());
  35.         return result;
  36.     }
  37. };

Java

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public List<Integer> postorderTraversal(TreeNode root) {
  12.         List<Integer> result = new ArrayList<Integer>();
  13.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  14.         if (root != null) stack.push(root);
  16.         while (!stack.isEmpty()) {
  17.             TreeNode curr = stack.pop();
  18.             result.add(curr.val);
  19.             if (curr.left != null) stack.push(curr.left);
  20.             if (curr.right != null) stack.push(curr.right);
  21.         }
  23.         Collections.reverse(result);
  24.         return result;
  25.     }
  26. }

源码分析

注意入栈的顺序和最后转置即可。

复杂度分析

同先序遍历。

Reference