题目描述

解题思路

专题组的二叉树有详细分析🔗

class Solution {
     public TreeNode buildTree(int[] preorder, int[] inorder) {
         /*   Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
            Output: [3,9,20,null,null,15,7]*/
            return traversal(inorder, 0, inorder.length, preorder, 0, preorder.length);
        }
        public TreeNode traversal(
                int[] inorder, int inLeft, int inRight,
                int[] preorder, int preLeft, int preRight
        ) {
            // 数组大小为0
            if (inRight - inLeft == 0) {
                return null;
            }
            // 数组大小只有一个
            if (inRight - inLeft == 1) {
                return new TreeNode(inorder[inLeft]);
            }
            int rootValue = preorder[preLeft];  // 获取分割元素
            int rootIndex = 0;
            // 查找分割元素在中序遍历数组的索引
            for (int i = 0; i < inRight; i++) {
                if (inorder[i] == rootValue) {
                    rootIndex = i;
                    break;
                }
            }
            // 生成此节点
            TreeNode root = new TreeNode(rootValue);
            // 递归调用
       /*   Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
            Output: [3,9,20,null,null,15,7]*/
            // 按照左闭右开分割
            root.left = traversal(inorder, inLeft, rootIndex,
                    preorder, preLeft + 1, preLeft + (rootIndex - inLeft) + 1);
            root.right = traversal(inorder, rootIndex + 1, inRight,
                    preorder, preLeft + (rootIndex - inLeft) + 1, preRight);
            return root;
        }
}