题解 | #重建二叉树#

重建二叉树

http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

前序遍历的第一个当前二叉树的头节点,寻找中序遍历中头节点划分左右子树,递归的建立左右子树

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        return build(pre, 0, pre.length-1, vin, 0, vin.length-1);
    }
    public TreeNode build(int[] pre, int preStart, int preEnd, int[] vin, int vinStart, int vinEnd){
        if(preStart>preEnd){
            return null;
        }
        
        TreeNode root=new TreeNode(pre[preStart]);
        int mid=vinStart;
        for(int i=vinStart; i<=vinEnd; i++){
            if(vin[i]==pre[preStart]){
                mid=i;
                break;
            }
        }
        root.left=build(pre, preStart+1, preStart+(mid-vinStart), vin, vinStart, mid-1);
        root.right=build(pre, preStart+(mid-vinStart)+1, preEnd, vin, mid+1, vinEnd);
        return root;
    }
}
全部评论

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务