Construct Binary Tree from Preorder and Inorder Traversal

给一个pre order和 in order遍历的数组, 返回一个二叉树.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree0(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    private TreeNode buildTree0(int[] preorder, int ipre, int jpre, int[] inorder, int iin, int jin) {
        if(jpre <= ipre || jin <= iin) return null;
        TreeNode root = new TreeNode(preorder[ipre]);
        int i=iin;
        for(; i<jin; i++) {
            if(inorder[i] == preorder[ipre]) break;
        }
        root.left = buildTree0(preorder, ipre+1, ipre+1+i-iin, inorder, iin, i);
        root.right = buildTree0(preorder, ipre+1+i-iin, jpre, inorder, i+1, jin);
        return root;
    }
}

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

public class Solution {

public TreeNode buildTree(int[] preorder, int[] inorder) {

return buildTree0(preorder, 0, preorder.length, inorder, 0, inorder.length);

}

private TreeNode buildTree0(int[] preorder, int ipre, int jpre, int[] inorder, int iin, int jin) {

if(jpre <= ipre || jin <= iin) return null;

TreeNode root = new TreeNode(preorder[ipre]);

int i=iin;

for(; i<jin; i++) {

if(inorder[i] == preorder[ipre]) break;

}

root.left = buildTree0(preorder, ipre+1, ipre+1+i-iin, inorder, iin, i);

root.right = buildTree0(preorder, ipre+1+i-iin, jpre, inorder, i+1, jin);

return root;

}

Construct Binary Tree from Preorder and Inorder Traversal

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags