Binary Tree的题目总结(四)

本文列举leetcode中两个关于构造二叉树的题目。
1，Construct Binary Tree from Inorder and Postorder Traversal
已知中序遍历序列，和后序遍历序列，通过这两个序列构造二叉树。

通过后序遍历序列的最后元素，我们总能找到根节点，然后通过这个值可以将中序序列分为两部分，然后在递归左右两部分。代码如下：

/**
 * 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[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) 
            return null;
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        int i = 0;
        for(i = 0; i < inorder.length; i++) {
            if(inorder[i] == postorder[postorder.length-1])
                break;
        }
        int[] lp = Arrays.copyOfRange(postorder, 0, i);
        int[] li = Arrays.copyOfRange(inorder, 0, i);
        int[] rp = Arrays.copyOfRange(postorder, i, postorder.length - 1);
        int[] ri = Arrays.copyOfRange(inorder, i + 1, inorder.length);
        root.left = buildTree(li, lp);
        root.right = buildTree(ri, rp);
        return root;
    }
}

2，Construct Binary Tree from Preorder and Inorder Traversal
已知中序遍历序列和前序遍历序列，构造二叉树

和上一题类似，我们从前序遍历序列中的第一位元素，来将中序序列分为两部分，即分别为根节点的左子树和右子树，递归左子树和右子树，代码如下：

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