145. Binary Tree Postorder Traversal.md

145. Binary Tree Postorder Traversal

---

leetcode-cn Daily Challenge on September 29th, 2020.

---

Difficulty : Medium

Related Topics : Stack、Tree

---

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 = []
Output: []

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up:

• Recursive solution is trivial, could you do it iteratively?

---

Solution

• mine
  • Java

    • Iterate Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.5 MB, less than 5.63% of Java online submissions

      //O(N)time O(N)space
      //N is node count
      public List<Integer> postorderTraversal(TreeNode root) {
          List<Integer> res = new LinkedList<>();
          LinkedList<TreeNode> stack = new LinkedList<>();
          TreeNode cur = root;
          while (cur != null || !stack.isEmpty()) {
              if (cur != null) {
                  stack.add(new TreeNode(cur.val));
                  if (cur.right != null) {
                      stack.add(cur.right);
                  }
                  cur = cur.left;
              } else {
                  cur = stack.getLast();
                  if (cur.right == null && cur.left == null) {
                      res.add(stack.removeLast().val);
                      cur = null;
                  } else {
                      cur  = stack.removeLast();
                  }
              }
          }
          return res;
      }
      

    • Recursive Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.7 MB, less than 5.63% of Java online submissions

      //O(N)time O(D)space
      //N is node count
      //D is root deep
      public List<Integer> postorderTraversal(TreeNode root) {
          List<Integer> res = new LinkedList<>();
          dfs(root, res);
          return res;
      }
      public void dfs(TreeNode node, List<Integer> list){
          if(node == null){
              return;
          }
          dfs(node.left,list);
          dfs(node.right,list);
          list.add(node.val);
      }
      

---

• the most votes

• Iterate Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.7 MB, less than 5.63% of Java online submissions

  //O(N)time O(N)space
  //N is node count
  public List<Integer> postorderTraversal(TreeNode root) {
      LinkedList<Integer> result = new LinkedList<>();
      Deque<TreeNode> stack = new ArrayDeque<>();
      TreeNode p = root;
      while(!stack.isEmpty() || p != null) {
          if(p != null) {
              stack.push(p);
              result.addFirst(p.val);  // Reverse the process of preorder
              p = p.right;             // Reverse the process of preorder
          } else {
              TreeNode node = stack.pop();
              p = node.left;           // Reverse the process of preorder
          }
      }
      return result;
  }
  

---

• the leetcode's solution

• Iterate Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.5 MB, less than 5.63% of Java online submissions

  //O(N)time O(N)space
  //N is node count
  public List<Integer> postorderTraversal(TreeNode root) {
      LinkedList<TreeNode> stack = new LinkedList<>();
      LinkedList<Integer> output = new LinkedList<>();
      if (root == null) {
        return output;
      }
  
      stack.add(root);
      while (!stack.isEmpty()) {
        TreeNode node = stack.pollLast();
        output.addFirst(node.val);
        if (node.left != null) {
          stack.add(node.left);
        }
        if (node.right != null) {
          stack.add(node.right);
        }
      }
      return output;
  }
  

---