【二叉树】重建二叉树（先序找根，中序分治）

题目描述

题目链接：JZ7 重建二叉树

解决思路

先序遍历：根左右； 中序遍历：左根右

• 通过前序序列创建根节点：pre[preLeft]

• 接着在中序序列中找到根节点的位置mid，通过mid划分左右子树：左子树节点个数为left_count，右子树为right_count；通过递归和分治思想，完成根节点的左右子树的构建。

  • 左子树的中序序列区间为[vinLeft,vin_mid)，先序序列区间为[vin_mid+1,vinRight)；
  • 右子树的中序序列区间为[preLeft + 1,preLeft + left_count + 1)，先序序列区间为[preLeft + left_count + 1,preRight)；

  这里注意先序子序列和中序子序列的区间均是左开右闭。

参考代码

//AC Code
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 int getIndex(int []vin, int l,int r, int val){
    
        for(int i = l; i < r; ++i){
    
            if(vin[i] == val){
    
                return i;
            }
        }
        return -1;
    }
    
    //通过先序序列确定根节点，通过中序序列中根节点的位置划分left和right（区间为[vinLeft,vinRight),[preLeft,preRight))）
    public TreeNode construct(TreeNode root, int []pre, int []vin, int vinLeft, int vinRight, int preLeft, int preRight){
    
        
        if(vinLeft >= vinRight || preLeft >= preRight){
    
            return null;
        }
        
        root = new TreeNode(pre[preLeft]);  //先序遍历第一个值作为根节点
        int vin_mid = getIndex(vin, vinLeft, vinRight, pre[preLeft]);  //pre[preLeft]为根节点，获取根节点在中序序列中的索引位置
        int left_count = Math.max(0,vin_mid - vinLeft);  //根节点左子树节点个数
        int right_count = Math.max(0,vinRight - vin_mid);   //根节点右子树节点个数
        root.left = construct(root.left, pre, vin, vinLeft, vin_mid, preLeft + 1, preLeft + left_count + 1);  //构建左子树
        root.right = construct(root.right, pre, vin, vin_mid + 1, vinRight, preLeft + left_count + 1, preRight);   //构建右子树
        return root;
    }
    
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
    
        
        if(pre.length == 0){
    
            return null;
        }
          
        TreeNode root = null;
        int vinLeft = 0, vinRight = vin.length, preLeft = 0, preRight = pre.length;
        root = construct(root, pre, vin, vinLeft, vinRight, preLeft, preRight);
        return root;
    }
}