二刷剑指Offer面试题07:重建二叉树

自己写的,思路是,对于一个节点,它的前序遍历,这个节点之后先跟着他左边的结点,再跟着它右边的结点。对于中序遍历,这个节点左面的,是他的左面的结点,右面的,是他右面的结点。

因此,按照前序的顺序,从前往后,并按照其所在中序的位置,找到前序中,以这个节点为根节点,分开的左右部分,递归建立。

 

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int index=-1;
        for(int count = 0;count<inorder.length;count++){
            if(inorder[count]==root.val){
                index = count;
            }
        }
        root.left = findNode(preorder,1,index,inorder,0,index-1);
        root.right = findNode(preorder,index+1,preorder.length-1,inorder,index+1,inorder.length-1);
        return root;
    }
    public TreeNode findNode(int[] preorder, int pre_s,int pre_e,int[] inorder,int in_s,int in_e){
        if(pre_s>pre_e||in_s>in_e){
            return null;
        }else if(pre_s==pre_e&&in_s==in_e){
            return new TreeNode(preorder[pre_s]);
        }
        TreeNode root = new TreeNode(preorder[pre_s]);
        int index=-1;
        for(int count = in_s;count<=in_e;count++){
            if(inorder[count]==root.val){
                index = count;
            }
        }
        root.left = findNode(preorder,pre_s+1,pre_s+index-in_s,inorder,in_s,index-1);
        root.right = findNode(preorder,pre_s+index-in_s+1,pre_e,inorder,index+1,in_e);
        return root;
    }
}

 

上一篇:[leetcode刷题]——剑指offer


下一篇:二叉树