105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

本题通过前序和中序来推断这个二叉树，一定会用到递归的方法，同时需要思考一下递归和动态规划的区别是什么，如果子问题之间相互之间是相互独立的，就需要使用递归的方法，而如果子问题之间是不是相互独立的，就需要使用动态规划的算法。我们要考虑的首先是递归的参数是什么，本题是preorder和inorder的参数应该分别都给出什么，发现preorder只要给出开始的索引就可以，inorder需要给出开始和结束索引，因为inorder要给函数进行递归，代码如下：

 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     public TreeNode buildTree(int[] preorder, int[] inorder) {
12         return helper(0,0,inorder.length-1,preorder,inorder);
13     }
14     public TreeNode helper(int preStart,int inStart,int inEnd,int[] preorder,int[] inorder){
15         if(preStart>preorder.length-1||inStart>inEnd) return null;
16         TreeNode root = new TreeNode(preorder[preStart]);
17         int indexIn = 0;
18         for(int i=inStart;i<=inEnd;i++){
19             if(inorder[i]==root.val) indexIn = i;
20         }
21         root.left = helper(preStart+1,inStart,indexIn-1,preorder,inorder);
22         root.right = helper(preStart+indexIn-inStart+1,indexIn+1,inEnd,preorder,inorder);
23         return root;
24     }
25 }

105. Construct Binary Tree from Preorder and Inorder Traversal

推荐阅读