[leetcode]_根据二叉树的先序遍历(后序遍历) + 中序遍历重建二叉树

题目1：Construct Binary Tree from Preorder and Inorder Traversal

给定一棵二叉树的先序遍历和中序遍历，求重建二叉树。

思路：

　　1、先序遍历的第一个节点一定是根节点。

　　2、在中序遍历中找到该根节点的位置（由中序遍历性质，决定其在中部），将中序遍历数组划分为两段，根节点左端的为左子树部分，相反右端的为右子树部分。

　　3、由上述左、右子树的长度，决定在先序遍历中，左右子树对应数组的位置。

　　4、递归 1 ~ 3步，直到子数组长度为1，结束递归。

代码：

 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     }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

题目二：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     }

这两道题思路理清了，到也很流畅。：)

[leetcode]_根据二叉树的先序遍历(后序遍历) + 中序遍历 重建二叉树

[leetcode]_根据二叉树的先序遍历(后序遍历) + 中序遍历重建二叉树