原題鏈接在這里：https://leetcode.com/problems/binary-tree-postorder-traversal/

題目：

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?

題解：

類似Binary Tree Inorder Traversal?和?Binary Tree Preorder Traversal.

Method 1: ?Recursion

Time Complexity: O(n). Space: O(logn).

AC 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 //Method 1: Recursion 12 public List<Integer> postorderTraversal(TreeNode root) { 13 //Recursion 14 List<Integer> ls = new ArrayList<Integer>(); 15 helper(root,ls); 16 17 return ls; 18 } 19 private void helper(TreeNode root,List<Integer> ls){ 20 if(root == null){ 21 return; 22 } 23 helper(root.left,ls); 24 helper(root.right,ls); 25 ls.add(root.val); 26 } 27 }

Method 2: Iteration + Stack

和Preorder, Inorder 類似.

當棧頂點右側為空 或者 右側已經traverse 過了, 就可以把棧頂?shù)狞c加入res中.?節(jié)點pre用來記載剛剛加入res的點, 可以用來判定右側是否已經traverse過了.

top.right == pre 說明right已經加入res里了.

Time Complexity: O(n), 每個點訪問了一次. Space:O(logn).

AC 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 class Solution { 11 public List<Integer> postorderTraversal(TreeNode root) { 12 List<Integer> res = new ArrayList<Integer>(); 13 Stack<TreeNode> stk = new Stack<TreeNode>(); 14 TreeNode pre = null; 15 while(root != null || !stk.isEmpty()){ 16 if(root != null){ 17 stk.push(root); 18 root = root.left; 19 }else{ 20 TreeNode top = stk.peek(); 21 if(top.right == null || top.right == pre){ 22 res.add(top.val); 23 stk.pop(); 24 pre = top; 25 }else{ 26 root = top.right; 27 } 28 } 29 } 30 return res; 31 } 32 }

?

轉載于:https://www.cnblogs.com/Dylan-Java-NYC/p/4825025.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的LeetCode 145. Binary Tree Postorder Traversal的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。