105-从前序与中序遍历序列构造二叉树

刺骨的言语ヽ痛彻心扉 2022-01-15 15:19 137阅读 0赞

**题目描述**

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

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

例如，给出
    
    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    返回如下的二叉树：
    
        3
       / \
      9  20
        /  \
       15   7

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal][https_leetcode-cn.com_problems_construct-binary-tree-from-preorder-and-inorder-traversal]

**解题过程**

*  分治法

class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder.length == 0 || inorder.length == 0)
            	return null;
            
            int temp = preorder[0];
            TreeNode res = new TreeNode(temp);
            int flag = 0;
            for(int i = 0;i < inorder.length;i++){
            	if(inorder[i] == temp){
            		flag = i;
            		break;
            	}
            }
            int[] left_inorder = Arrays.copyOfRange(inorder, 0, flag);    
            int[] left_pre = Arrays.copyOfRange(preorder, 1, left_inorder.length + 1);
            int[] right_inorder = Arrays.copyOfRange(inorder, flag + 1, inorder.length);
            int[] right_pre = Arrays.copyOfRange(preorder, left_inorder.length + 1, preorder.length);
            res.left = null;
            res.left = buildTree(left_pre, left_inorder);
            
            res.right = null;
            res.right = buildTree(right_pre, right_inorder);
            
            return res;
        }
    }

[https_leetcode-cn.com_problems_construct-binary-tree-from-preorder-and-inorder-traversal]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal