求 889 容易明白的代碼

感謝。

這題我做了半天....  求Java 容易理解的代碼

思想就是先把左边和右边的partition分别找出来， 然后递归找到他们的root。

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode() {}
   
8. *     TreeNode(int val) { this.val = val; }
   
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
   
10. *         this.val = val;
    
11. *         this.left = left;
    
12. *         this.right = right;
    
13. *     }
    
14. * }
    
15. */
    
16. class Solution {
    
17.     public TreeNode constructFromPrePost(int[] pre, int[] post) {
    
18.         
    
19.         int n = pre.length;
    
20.         int m = post.length;
    
21.         if(m != n || n == 0) return(null);
    
22.         //System.out.println(Arrays.toString(pre));
    
23.         //System.out.println(Arrays.toString(post));
    
24.         TreeNode root = new TreeNode(pre[0]);
    
25.         if(n == 1) return(root);
    
26.         int[] preLoc = new int[31];
    
27.         int[] postLoc = new int[31];
    
28.         for(int i = 0; i < n; i++){
    
29.             preLoc[pre[i]] = i;
    
30.             postLoc[post[i]] = i;
    
31.         }
    
32.         int leftRootVal = pre[1];
    
33.         int leftLen = postLoc[leftRootVal] + 1;
    
34.         int rightLen = n - 1 - (postLoc[leftRootVal] + 1);
    
35.         //System.out.println(leftLen);
    
36.         //System.out.println(rightLen);
    
37.         root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, leftLen + 1), Arrays.copyOfRange(post, 0, leftLen));
    
38.         root.right = constructFromPrePost(Arrays.copyOfRange(pre, leftLen + 1, n), Arrays.copyOfRange(post, leftLen, n - 1));
    
39.         return(root);
    
40.     }
    
41. 
    
42. }

复制代码

跟你分享个 Python 的答案吧，不用搞什么 partition. 就建立一个 stack, pre 里面的东西拿到就做成 node 放到 stack 里。末尾跟 post 一样就 pop, pop 的时候再建立连接。最后返回最后一次 pop 的节点。快得很。关键是那个 while 比较 tricky. 时间复杂度明显 O(n).

1.     def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
   
2.         s = []
   
3.         i = 0
   
4.         for a in pre:
   
5.             n = TreeNode(a)
   
6.             s.append(n)
   
7.             while s and s[-1].val == post[i]:
   
8.                 i += 1
   
9.                 n = s.pop()
   
10.                 if s:
    
11.                     parent = s[-1]
    
12.                     if not parent.left:
    
13.                         parent.left = n
    
14.                     else:
    
15.                         parent.right = n
    
16.         return n

复制代码

[/i]

謝謝各位!!! 我已經把答案整理好了！！

1. class Solution {
   
2.    
   
3.     public TreeNode constructFromPrePost(int[] pre, int[] post) {
   
4.         
   
5.         Map<Integer, Integer> map = new HashMap<>();
   
6.         
   
7.         for (int i = 0; i < post.length; i++){
   
8.             map.put(post[i], i);
   
9.         }
   
10.         
    
11.         return dfs(pre, 0, pre.length - 1,
    
12.                    post, 0, post.length - 1,
    
13.                    map);
    
14.     }
    
15.    
    
16.     private TreeNode dfs(int[] pre,  int preStart, int preEnd,
    
17.                          int[] post, int postStart, int postEnd,
    
18.                          Map<Integer, Integer> map)
    
19.     {
    
20.         
    
21.         if (preStart > preEnd || postStart > postEnd) return null;
    
22.          
    
23.         TreeNode root = new TreeNode(pre[preStart]);
    
24.         
    
25.         if (preStart == preEnd ) return root;
    
26.      
    
27.         /*  pre = [1,           2,4,5,3,6,7]
    
28.             post = [4,5,2,6,7,3,           1]
    
29.         */
    
30.          
    
31.         int deltaIndex = map.get( pre[ preStart+1 ] ) - postStart;
    
32. 
    
33.         root.left = dfs(pre, preStart + 1, preStart + 1 + deltaIndex,
    
34.                         post, postStart, postStart + deltaIndex,
    
35.                         map);
    
36. 
    
37.         root.right = dfs(pre,  preStart + 1 + deltaIndex + 1, preEnd,
    
38.                          post, postStart + deltaIndex + 1, postEnd - 1,
    
39.                          map);
    
40.          
    
41.         return root;
    
42.     }
    
43. }

复制代码

techDiscussion 发表于 2021-1-5 02:29
謝謝各位!!! 我已經把答案整理好了！！
[mw_shl_code=java,true]class Solution {
   

node值比较小 可以不用map。

iaukeit 发表于 2021-1-5 06:13
node值比较小 可以不用map。

那用什麼?

techDiscussion 发表于 2021-1-5 11:50
那用什麼?

就用array存就好了，一般来说array占用内存少 速度也会快一些。

iaukeit 发表于 2021-1-5 20:30
就用array存就好了，一般来说array占用内存少 速度也会快一些。

明白，你意思是說，把value當坐標，把index當array的值，對嘛？

techDiscussion 发表于 2021-1-5 11:50
那用什麼?

map的本质是什么？  就是个key value pair.  在key 的空间太大的时候用各种hash算法， key的可能性很小的时候就上数组了， 数组性能更好，代码也简单。