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

2019-06-12  本文已影响0人  皮蛋豆腐酱油
/**
 * 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) {
         TreeNode root = reConstructBinaryTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
         return root;
    }
    
    private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) { 
        if (startPre > endPre || startIn > endIn) { return null; }
        TreeNode root = new TreeNode(pre[startPre]); 
        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == pre[startPre]) { 
                root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1); 
                root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
                break;
            } 
        }
        return root; 
    }

}
上一篇 下一篇

猜你喜欢

热点阅读