|
?
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
来源：力扣（LeetCode）
?
????????解题思路：因为不知道数组的长度，首先需要先判断数组是不是为空或者长度为0（感觉还应该判断两数组是不是长度一样，是不是符合题意前序与中序的对应关系，代码中暂时没有做到。想实现也简单，在主方法中判断长度是否一样，在递归方法中get下标前加一句判断map中有没有这个key）。
? ? ? ? 之后构建递归，每次必要传入的数为：
????????1.递归inorder数组的左右界限，也就是这个子树在哪个范围内。
? ? ? ? 2.preindex，表示此次递归父节点在preorder的下标，有了preorder数组中的下标能得到这个父节点的value值。
????????递归的时候返回子树根节点的对象。在上一次递归中连接到某节点的左右节点。
????????如果输入的数据中 left>right ，则自动返回null。在上一次递归中某节点左右节点连接null。? ? ??
????????注意在递归前没有判断输入的下标是不是越界了。因此需要在连接左右节点的时候加上判断。如果越界了，说明已经超过数组了，就连接null就行了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
HashMap<Integer, Integer> hash1;
int[] preorder;
int[] inorder;
public TreeNode buildTree ( int[] preorder , int[] inorder ) {
if ( preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0 ) {
return null;
}
hash1 = new HashMap<Integer, Integer> ( );
this.preorder = preorder;
this.inorder = inorder;
for ( int i = 0 ; i < inorder.length ; i++ ) {
hash1.put ( inorder[ i ] , i );
}
return setTree ( preorder[ 0 ] , 0 , inorder.length - 1 , 0 );
}
public int getIndex ( int num ) {
return hash1.get ( num );
}
//使用递归 用inorder数组递归，需要输入左右边界和中间父节点的位置
public TreeNode setTree ( int num , int left , int right , int preindex ) {
if ( left > right ) {
return null;
}
int mid = getIndex ( num );
TreeNode node = new TreeNode ( num );
node.left = preindex + 1 < preorder.length ? setTree ( preorder[ preindex + 1 ] , left , mid - 1 , preindex + 1 ) : null;
node.right = mid - left + preindex + 1 < preorder.length ? setTree ( preorder[ mid - left + preindex + 1 ] , mid + 1 , right , mid - left + preindex + 1 ) : null;
return node;
}
}
|