udpate

dingjikerbo · dingjikerbo · commit 036597d02f29 · 2018-12-09T15:54:46.000+08:00
diff --git a/leetcode/solution/src/BinaryTreePostorderTraversal.java b/leetcode/solution/src/BinaryTreePostorderTraversal.java
@@ -1,7 +1,4 @@
-import java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.LinkedList;
-import java.util.List;
+import java.util.*;
 
 public class BinaryTreePostorderTraversal {
 
@@ -25,4 +22,67 @@ public List<Integer> postorderTraversal(TreeNode root) {
         }
         return results;
     }
+
+
+    public ArrayList<Integer> postorderTraversal2(TreeNode root) {
+        ArrayList<Integer> result = new ArrayList<Integer>();
+        Stack<TreeNode> stack = new Stack<TreeNode>();
+        TreeNode prev = null; // previously traversed node
+        TreeNode curr = root;
+
+        if (root == null) {
+            return result;
+        }
+
+        stack.push(root);
+        while (!stack.empty()) {
+            curr = stack.peek();
+            if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
+                if (curr.left != null) {
+                    stack.push(curr.left);
+                } else if (curr.right != null) {
+                    stack.push(curr.right);
+                }
+            } else if (curr.left == prev) { // traverse up the tree from the left
+                if (curr.right != null) {
+                    stack.push(curr.right);
+                }
+            } else { // traverse up the tree from the right
+                result.add(curr.val);
+                stack.pop();
+            }
+            prev = curr;
+        }
+
+        return result;
+    }
+
+    public List<Integer> postorderTraversal3(TreeNode root) {
+        List<Integer> result = new ArrayList<>();
+
+        if (root == null) {
+            return result;
+        }
+
+        Stack<TreeNode> stack = new Stack<>();
+
+        TreeNode last = null;
+
+        while (!stack.isEmpty() || root != null) {
+            if (root != null) {
+                stack.push(root);
+                root = root.left;
+            } else {
+                TreeNode peek = stack.peek();
+                if (peek.right != null && last != peek.right) {
+                    root = peek.right;
+                } else {
+                    result.add(peek.val);
+                    last = stack.pop();
+                }
+            }
+        }
+
+        return result;
+    }
 }
diff --git a/leetcode/solution/src/BinaryTreeUpsideDown.java b/leetcode/solution/src/BinaryTreeUpsideDown.java
@@ -3,6 +3,7 @@ public class BinaryTreeUpsideDown {
     /**
      * 将root的左子树看作一个整体，root.left就作为倒置后的root和root.right的新parent
      * 注意若root的左子树为空，则无法倒置了，什么也不做
+     * 注意最后要给root的左右清零
      */
     public TreeNode upsideDownBinaryTree(TreeNode root) {
         if(root == null || root.left == null) {
diff --git a/leetcode/solution/src/Codec.java b/leetcode/solution/src/Codec.java
@@ -50,7 +50,7 @@ private TreeNode helper(Queue<String> queue) {
         return root;
     }
 
-    /** 下面是非递归版的DFS */
+    /** 下面是非递归版的，前序遍历 */
     public String serialize2(TreeNode root) {
         StringBuilder sb = new StringBuilder();
         if (root == null) {
@@ -74,7 +74,10 @@ public String serialize2(TreeNode root) {
         return sb.toString();
     }
 
-    // Decodes your encoded data to tree.
+    /**
+     * 前序访问一遍所有结点
+     * 在设置node时，从queue中取出值
+     */
     public TreeNode deserialize2(String data) {
         String[] texts = data.split(SEP);
         Queue<String> queue = new LinkedList<String>(Arrays.asList(texts));
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -6,12 +6,12 @@ public class Main {
 
     public static class Solution {
 
+        public int sumOfLeftLeaves(TreeNode root) {
 
-
+        }
     }
 
     public static void main(String[] args) {
         Solution s = new Solution();
-        System.out.println(a);
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -6,12 +6,12 @@ public class Main {`
`6`	`6`
`7`	`7`	`public static class Solution {`
`8`	`8`
	`9`	`+ public int sumOfLeftLeaves(TreeNode root) {`
`9`	`10`
`10`		`-`
	`11`	`+ }`
`11`	`12`	`}`
`12`	`13`
`13`	`14`	`public static void main(String[] args) {`
`14`	`15`	`Solution s = new Solution();`
`15`		`- System.out.println(a);`
`16`	`16`	`}`
`17`	`17`	`}`