No. 145 - Binary Tree Postorder Traversal
====


---

## [LeetCode 145 -- Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)

### 題目描述

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

Example 1.


Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2.


Input: root = [1,2]
Output: [2,1]

---

Tree traversal 的題目，都會分別講解 recursive 及 iterative 的解法:

### 解法 1. Recursive Approach

Postorder traversal 就是***先走訪左子樹，再走訪右子樹，再走訪父節點***。

完整的程式碼如下面所示

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traverse(TreeNode *node, vector<int> &res) {
      if (node) {
        traverse(node->left, res);
        traverse(node->right, res);
        res.push_back(node->val);
      }
    }
    vector<int> postorderTraversal(TreeNode* root) {
      vector<int> res;
      traverse(root, res);
      return res;
    }
};

我們可以用下面的例子來看出 `traverse` 函式是怎麼運作的

    [1]
    / \
   2   3
  / \   \
 4   5   6
 traverse(1)
 
     1
    / \
  [2]  3
  / \   \
 4   5   6
 traverse(1) -> traverse(2)
 
     1
    / \
   2   3
  / \   \
[4]  5   6 
 traverse(1) -> traverse(2) -> traverse(4)
 res = [4]
 
     1
    / \
  [2]  3
  / \   \
 4   5   6  
 traverse(1) -> traverse(2)
 
     1
    / \
   2   3
  / \   \
 4  [5]  6  
 traverse(1) -> traverse(2) -> traverse(5)
 res = [4, 5]
 
     1
    / \
  [2]  3
  / \   \
 4   5   6 
 traverse(1) -> traverse(2)
 res = [4, 5, 2]
 
 
    [1]
    / \
   2   3
  / \   \
 4   5   6 
 traverse(1)
 
     1
    / \
   2  [3]
  / \   \
 4   5   6
 traverse(1) -> traverse(3)
 
     1
    / \
   2   3
  / \   \
 4   5  [6] 
 traverse(1) -> traverse(3) -> traverse(6)
 res = [4, 5, 2, 6]
 
     1
    / \
   2  [3]
  / \   \
 4   5   6 
 traverse(1) -> traverse(3)
 res = [4, 5, 2, 6, 3]
 
    [1]
    / \
   2   3
  / \   \
 4   5   6  
 traverse(1)
 res = [4, 5, 2, 6, 3, 1]

由於 postorder traversal 是最後才走訪父節點，所以一定都是當 `traverse` 函式沒辦法往該 node 的左或右做 traverse 的時候才會存到 `res`。

### 解法 2. Iterative Approach

接著來講解 iterative 的作法，其程式碼如下

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

我們首先會在每次走訪到的 node 先確認其 left child 存不存在，再確認 right child 存不存在，因為 postorder 會先走訪左子樹再走訪右子樹。而不管 left 或 right child 哪邊存在，判斷完後我們一定會把當前的 node 存到 stack 裡 (第 20, 25 行) 好讓之後能走訪完子樹後能回到此 node。當判斷完要走訪哪邊並且把 node 存到 stack 之後，我們需要把此 node 要走訪 left 或 right 的指標改成 `nullptr` (第 22, 27 行) 以記錄這個 node 已經走訪過那一邊。

若當前的 node 已經沒有左右子樹可以走訪則會把該 node 的值存到 `res` 也就是最後走訪父節點的意思 (第 30 行)，接著我們要檢查 stack 裡面還有沒有 node，如果還有代表還有 node 的右子樹還沒走訪或者其 node 還沒被存到 `res`，我們就要回到該 node 繼續走訪其右子樹或者存到 `res`。

為什麼從 stack pop 出來的 node 不會走訪左子樹呢? 因為 postorder traversal 會先走訪左子樹，所以再次回到 stack 中存的 node 其左子樹一定已經走訪過了。

### 複雜度分析

時間複雜度分析上，不論是 recursive 還是 iterative 的作法都是要走訪所有的 nodes，所以時間複雜度為 $O(N)$。

空間複雜度分析上，recursive 的方法需要 stack 來存 `traverse` 函式讓之後可以跳回前一個 `traverse` 函式，而 `traverse` 函式最多連續呼叫的次數就是 tree 的高度，所以空間複雜度需要 $O(H)$，$H$ 為 tree 的高。我們可以回去看前面的範例說明，範例中的 tree 高度為 3，所以可以看到最多連續呼叫的 `traverse` 函式也是 3。

若不是在這種全部偏左或右的極端情況下，平均情況下空間複雜度為 $O(\log N)$。

而 iterative 的作法空間複雜度也是 $O(H)$，因為每次走訪到左子樹或右子樹的尾端後就會把之前存在 stack 的 node pop 出來，所以 stack 最多只會存到 tree 的高度的 node 數量，這邊跟 recursive 的不同在於存的是函式還是 node。

:::info
學會了 preoder traversal，另外還有 inorder traversal 跟 postorder traversal 哦! 請看 [94. Binary Tree Inorder Traversal](https://hackmd.io/@Ji0m0/HyAgG6bU_) 及 [144. Binary Tree Preorder Traversal](https://hackmd.io/@Ji0m0/S1_VMT-L_)
:::