首页 > 代码库 > 【LeetCode题目记录-2】从前序遍历和中序遍历构建二叉树

【LeetCode题目记录-2】从前序遍历和中序遍历构建二叉树

Construct Binary Tree from Preorder and Inorder Traversal

 Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

【分析1-非原创】递归调用。

参考:http://bylijinnan.iteye.com/blog/1355279

    public static TreeNode buildTree(int[] preorderint[] inorder) {

        if (preorder == null || inorder == null) {

            return null;

        }

        return build(preorder, 0, preorder.length - 1, inorder, 0,

                inorder.length - 1);

    }

    /*递归建立二叉树,在preorder中获取根节点,在inorder查找根节点,获取一个偏移量offset是左子树的节点个数

     * 注意截止条件

     * */

    public static TreeNode build(int[] preorderint start1int end1,

            int[] inorderint start2int end2) {

        if (start1 > end1 || start2 > end2) {

            return null;

        }

        int rootVal = preorder[start1];

        TreeNode root = new TreeNode(rootVal);

        int divider = getDivider(inorderstart2end2rootVal);

        int offSet = divider - start2;

        TreeNode left = build(preorderstart1 + 1, start1 + offSetinorder,

                start2start2 + offSet - 1);

        TreeNode right = build(preorderstart1 + offSet + 1, end1inorder,

                divider + 1, end2);

        root.left = left;

        root.right = right;

        return root;

 

    }

 

    public static int getDivider(int[] inorderint startint endint arg) {

        for (int i = starti <= endi++) {

            if (inorder[i] == arg) {

                return i;

            }

        }

        return -1;

    }

【分析1-非原创】辅助Stack

参考:https://oj.leetcode.com/discuss/2297/the-iterative-solution-is-easier-than-you-think

【LeetCode题目记录-2】从前序遍历和中序遍历构建二叉树