java根据前序与中序遍历序列构造二叉树

叁歲伎倆 2024-03-16 11:18 25阅读 0赞

## 根据前序与中序遍历序列构造二叉树 ##

### 问题描述 ###

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

1 <= preorder.length <= 3000
    inorder.length == preorder.length
    -3000 <= preorder[i], inorder[i] <= 3000
    preorder 和 inorder 均 无重复 元素
    inorder 均出现在 preorder
    preorder 保证 为二叉树的前序遍历序列
    inorder 保证 为二叉树的中序遍历序列。

### 示例 ###

![在这里插入图片描述][473db952863942699c79f95f7b94dbde.png]

### 原题OJ链接 ###

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

### 解答代码 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            int inbegin = 0;
            int inend = inorder.length-1;
            return buildTreeChild(preorder,inorder,inbegin,inend);
    
        }
        public int i = 0;
        public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
        
            if(inbegin>inend){
        
                return null;
            }
            TreeNode root = new TreeNode(preorder[i]);
            int rootIndex = findIndex(inorder,inbegin,inend,preorder[i]);
            i++;
            root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
            root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
    
            return root;
    
        
        }
        private int findIndex(int[] inorder,int inbegin,int inend,int k){
        
            int j = inbegin;
            for(j = inbegin;j<= inend;j++){
        
                if(inorder[j] == k){
        
                    return j;
                }
            }
            return -1;
        }
    }

[473db952863942699c79f95f7b94dbde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/805ddc34978c489b8c144bc629122e26.png