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

本文主要是介绍二刷剑指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;
    }
}

这篇关于二刷剑指Offer面试题07：重建二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！