Binary Tree Postorder Traversal

Question

Problem Statement

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

Example

Given binary tree {1,#,2,3},

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

return [3,2,1].

Challenge

Can you do it without recursion?

題解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. }

源碼分析

遞迴版的太簡單了，沒啥好說的，注意入 Stack 順序。

複雜度分析

時間複雜度近似爲 O(n).

題解2 - 迭代

使用遞迴寫後序遍歷那是相當的簡單，我們來個不使用遞迴的迭代版。整體思路仍然爲「左右根」，那麼怎麼才能知道什麼時候該訪問根節點呢？問題即轉化爲如何保證左右子節點一定先被訪問到？由於入Stack之後左右節點已無法區分，因此需要區分左右子節點是否被訪問過(加入到最終返回結果中)。除了有左右節點的情況，根節點也可能沒有任何子節點，此時也可直接將其值加入到最終返回結果中。

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.         if (root == null) return result;
  15.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  16.         stack.push(root);
  17.         TreeNode prev = null;
  18.         while (!stack.isEmpty()) {
  19.             TreeNode curr = stack.peek();
  20.             boolean noChild = (curr.left == null && curr.right == null);
  21.             boolean childVisited = false;
  22.             if (prev != null && (curr.left == prev || curr.right == prev)) {
  23.                 childVisited = true;
  24.             }
  26.             if (noChild || childVisited) {
  27.                 result.add(curr.val);
  28.                 stack.pop();
  29.                 prev = curr;
  30.             } else {
  31.                 if (curr.right != null) stack.push(curr.right);
  32.                 if (curr.left != null) stack.push(curr.left);
  33.             }
  34.         }
  36.         return result;
  37.     }
  38. }

源碼分析

遍歷順序爲『左右根』，判斷根節點是否應該從Stack中剔除有兩種條件，一爲無子節點，二爲子節點已遍歷過。判斷子節點是否遍歷過需要排除prev == null 的情況，因爲 prev 初始化爲 null.

將遞迴寫成迭代的難點在於如何在迭代中體現遞迴本質及邊界條件的確立，可使用簡單示例和紙上畫出Stack調用圖輔助分析。

複雜度分析

最壞情況下Stack內存儲所有節點，空間複雜度近似爲 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 of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     /**
  14.      * @param root: The root of binary tree.
  15.      * @return: Postorder in ArrayList which contains node values.
  16.      */
  17.     public ArrayList<Integer> postorderTraversal(TreeNode root) {
  18.         ArrayList<Integer> result = new ArrayList<Integer>();
  19.         if (root == null) return result;
  21.         Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
  22.         stack.push(root);
  23.         while (!stack.isEmpty()) {
  24.             TreeNode node = stack.pop();
  25.             result.add(node.val);
  26.             if (node.left != null) stack.push(node.left);
  27.             if (node.right != null) stack.push(node.right);
  28.         }
  29.         Collections.reverse(result);
  31.         return result;
  32.     }
  33. }

源碼分析

注意入Stack的順序和最後轉置即可。

複雜度分析

同先序遍歷。

Reference