题解 | #重建二叉树#

重建二叉树

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;
    }
}
全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
Gaynes:查看图片
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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