JZ7 重建二叉树

JZ7 重建二叉树

重建二叉树_牛客题霸_牛客网 (nowcoder.com)

//11
//递归
//pre-根左右
//vin-左根右
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length==0||vin.length==0){
            return null;
        }
        TreeNode root=new TreeNode(pre[0]);
        for(int i=0;i<vin.length;i++){
            if(pre[0]==vin[i]){
                root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),
                                                Arrays.copyOfRange(vin,0,i));
                root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),
                                                Arrays.copyOfRange(vin,i+1,vin.length));
                break;
            }
        }
        return root;
    }
}


// //栈
// import java.util.*;
// public class Solution {
//     public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
//         if(pre.length==0||vin.length==0){
//             return null;
//         }
//         Stack<TreeNode> st=new Stack<>();
//         TreeNode root=new TreeNode(pre[0]);
//         TreeNode cur=root;
//         for(int i=1,j=0;i<pre.length;i++){
//             if(cur.val!=vin[j]){
//                 cur.left=new TreeNode(pre[i]);
//                 st.push(cur);
//                 cur=cur.left;
//             }else{
//                 j++;
//                 while(st.isEmpty()==false&&st.peek().val==vin[j]){
//                     cur=st.pop();
//                     j++;
//                 }
//                 cur.right=new TreeNode(pre[i]);
//                 cur=cur.right;
//             }
//         }
//         return root;
//     }
// }