重建二叉树

Love The Way You Lie 2022-05-14 15:48 227阅读 0赞

### 二叉树重建 ###

根据二叉树的前序遍历和中序遍历，重建二叉树。综合利用前序遍历和中序遍历的特点。

/*
     * 题目描述
    输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
    假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
    例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
    则重建二叉树并返回。
     */
    class TreeNode {
    	int val;
    	TreeNode left;
    	TreeNode right;
    
    	TreeNode(int x) {
    		val = x;
    	}
    }
    
    public class Test04 {
    	public static void main(String[] args) {
    		int[] pre = { 1, 2, 4, 7, 3, 5, 6, 8 };
    		int[] mid = { 4, 7, 2, 1, 5, 3, 8, 6 };
    		Solution04 solution = new Solution04();
    		TreeNode ret = solution.reConstructBinaryTree(pre, mid);
    		System.out.println(ret);
    	}
    }
    
    /*
     * ①：从前序遍历中找根节点，前序遍历第一个即为根节点 =》1 ②：然后中序遍历中1的左边为左子树，1的右边为右子树，然后继续递归，
     */
    class Solution04 {
    	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    		if(pre == null || in == null || pre.length ==0 || in.length ==0){
    			return null;
    		}
    		return buildTree(pre, 0, pre.length-1, in, 0, in.length-1);
    	}
    
    	public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
    		TreeNode root = new TreeNode(pre[preStart]);
    		int rootIn =0;//前序遍历特点，所以第一个一定为0;然后找根节点在中序遍历中的位置index
    		for(; rootIn<inEnd; ++rootIn){
    			if(in[rootIn] == root.val){
    				break;//直接break即可，此时rootIn中存储了中序数组中的根节点的位置
    			}
    		}
    		//算出中序数组中左子树的长度
    		int leftLength = rootIn - inStart; //不需要减一
    		//算出中序数组中右子树的长度
    		int rightLefth = inEnd-rootIn;
    		if(leftLength>0){//递归
    			//递归中，preStart+1属于第二次起始位置，到preStart+leftLength,  核心思想是把属于左子树的范围给他们
    			root.left = buildTree(pre, preStart+1, preStart+leftLength, in, inStart, rootIn-1);
    		}
    		if(rightLefth>0){//递归
    			//核心思想是把属于右子树的范围给右子树进行递归
    			root.right = buildTree(pre, preStart+leftLength+1, preEnd, in, rootIn+1, inEnd);
    		}
    		return root;
    	}
    }