[leetcode]_두 갈래 나무의 선순 반복(후순 반복) + 중순 반복에 따라 두 갈래 나무 재건

제목 1:Construct Binary Tree from Preorder and Inorder Traversal
두 갈래 나무의 선차적 역류와 중차적 역류를 정하여 두 갈래 나무를 재건하도록 하다.
생각:
1. 먼저 훑어보는 첫 번째 노드는 반드시 루트 노드이다.
2. 중서 역주행에서 이 뿌리 노드의 위치(중서 역주행 성질에 따라 중부에 결정)를 찾아 중서 역주행 수조를 두 단락으로 나누고 뿌리 노드의 왼쪽은 왼쪽 트리 부분이고 반대는 오른쪽 트리 부분이다.
3. 상술한 왼쪽, 오른쪽 트리의 길이에 따라 선행 반복에서 좌우 트리가 대응하는 수조의 위치를 결정한다.
4. 하위 그룹의 길이가 1이 될 때까지 1~3단계로 귀속한다.
코드:

 1 public TreeNode buildTree(int[] preorder, int[] inorder) {
 2         if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) return null;
 3         
 4         TreeNode root = buildTreeRecursive(preorder , 0 , preorder.length - 1 , inorder , 0 , inorder.length - 1);
 5         return root;
 6     }
 7     
 8     public TreeNode buildTreeRecursive(int[] preOrder , int preStart , int preEnd , int[] inOrder , int inStart , int inEnd){
 9         int value = preOrder[preStart]; 
10         //1、 。
11         TreeNode node = new TreeNode(value);
12         
13         // ： 1， 。
14         if(preStart == preEnd) return node;
15         
16         //2、 。
17         int index = 0;
18         for(index = inStart ; index <= inEnd && inOrder[index] != value; ){ index++; }
19         
20 
21         //3、 ， 。
22         int leftLen = index - inStart;
23         int rightLen = inEnd - index;
24         
25         if(leftLen > 0){
26             node.left = buildTreeRecursive(preOrder , preStart + 1 , preStart + leftLen , inOrder , inStart , index - 1);
27         }
28         if(rightLen > 0){
29             node.right = buildTreeRecursive(preOrder , preEnd - rightLen + 1 , preEnd , inOrder , index + 1 , inEnd);
30         }
31         
32         return node;
33     } 

 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
제목2:Construct Binary Tree from Inorder and Postorder Traversal
두 갈래 나무의 중차적 역류와 후차적 역류를 정해 두 갈래 나무를 재건한다.그 사고방식은 제목과 완전히 같다.단지postOrder에서 루트 노드의 위치를 확정하고 inOrder에 똑같이 놓아서 좌우 트리를 구분합니다.
코드:

 1    public TreeNode buildTree(int[] inorder, int[] postorder) {
 2         if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) return null;
 3         
 4         TreeNode root = buildTreeRecursive(inorder , 0 , inorder.length - 1 , postorder , 0 , postorder.length - 1);
 5         return root;
 6     }
 7     
 8     public TreeNode buildTreeRecursive(int[] inOrder , int inStart , int inEnd , 
　　　　　　　　　　　　　　　　　　　　　　　　 int[] postOrder , int postStart , int postEnd){
 9         
10         int value = postOrder[postEnd];
11         TreeNode node = new TreeNode(value);
12         if(postStart == postEnd) return node; // only one node
13         
14         int index = -1;
15         for(index = inStart ; index <= inEnd && inOrder[index] != value ; index++); // find in inOrder
16         
17         int leftLen = index - inStart;
18         if(leftLen > 0){
19             node.left = buildTreeRecursive(inOrder , inStart , index - 1 , postOrder , postStart , postStart + leftLen - 1);
20         }
21         int rightLen = inEnd - index;
22         if(rightLen > 0){
23             node.right = buildTreeRecursive(inOrder , index + 1 , inEnd , postOrder , postEnd - rightLen , postEnd - 1);
24         }
25         
26         return node;
27         
28     }

 
이 두 문제의 사고방식은 정리되었고 끝까지 유창하다.:)