LeetCode--已知前序遍历和中序遍历构造二叉树

雨点打透心脏的1/2处 2022-03-01 03:40 186阅读 0赞

题干：

根据一棵树的前序遍历与中序遍历构造二叉树。

**注意:**  
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

解答：

/**
     * 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 ;
            }
            if(preorder.length == 1){
                return new TreeNode(preorder[0]);
            }
            TreeNode root = new TreeNode(preorder[0]);
            int rootNum = 0 ;
            for(int i =0 ; i < inorder.length; i ++){
                if(inorder[i] == preorder[0]){
                    rootNum = i;
                    break;
                }
            }
            int[] inLeft = Arrays.copyOfRange(inorder,0,rootNum);
            int[] preLeft = Arrays.copyOfRange(preorder,1,1+inLeft.length);
            int[] inRight =  Arrays.copyOfRange(inorder,rootNum+1,inorder.length);
            int[] preRight = Arrays.copyOfRange(preorder,inorder.length-inRight.length,inorder.length);
            root.left = buildTree(preLeft,inLeft);
            root.right = buildTree(preRight,inRight);
        return root;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70][] 同名原创公众号： **程序大视界**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70]: /images/20220301/7da6759358e24716bfb4cb6ccace2a0f.png