构造二叉树

---

01 前序和中序遍历 构造二叉树

LeetCode 105

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

解题思路

解题思路 01

可以知道，前序遍历的第一个数，是二叉树的根节点，接下来查找中序遍历的根节点，则左边为左子树，右边为右子树。

刚开始创建一个哈希表<Integer, Integer >，键为中序遍历的元素值，值为其下标。 此目的是为了前序遍历传过来的根节点值来查找中序遍历中根节点的位置（下标）。

于是接下来定好构造左子树需要的条件则可递归下去重构二叉树。

• 一是需要前序遍历数组的左子树范围，可以用左右指针来划分大数组，即需要的那段（蓝色）的下标，用一左一右指针框起来，加下来递归使用。

• 二是需要中序遍历数组的左子树范围，也就是蓝色区域，同上，用双指针定好范围递归使用。

代码如下

/*class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}*/
public class Solution {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 先将中序遍历的数组存进map，给一个根节点的值，去找到根节点在中序遍历数组中的下标
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    // 分别传入前序遍历的左右指针确定范围，和中序遍历的左右指针
    public TreeNode build(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) return null;
        // 找到根节点在中序遍历的位置
        int inorder_root = map.get(preorder[preorder_left]);
        // 创建根节点用于返回，根的值为原二叉树的根节点值
        TreeNode root = new TreeNode(preorder[preorder_left]);
        // 剩余左子树的长度，用于确认接下来要传入的参数的值
        int leftTreeSize = inorder_root - inorder_left;
        // 看图说话，分别需要左子树（蓝色），就传入需要的前序和中序的范围，右子树（未标色）同理
        root.left = build(preorder, inorder, preorder_left + 1, preorder_left + leftTreeSize, inorder_left, inorder_root - 1);
        root.right = build(preorder, inorder, preorder_left + leftTreeSize + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
}  

02 中序和后序遍历 构造二叉树

LeetCode 106

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

解题思路

解题思路 02

方法与前中序遍历构造二叉树一样，在后序遍历的最后一个位置找到根节点的值，再根据哈希表找到根节点在中序遍历的位置，在中序遍历的根节点将左右子树划分在两个位置，然后递归构造二叉树，传入的双指针来确认中序遍历和后序遍历数组需要的范围。

代码如下

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
public class Solution {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    public TreeNode build(int[] inorder, int[] postorder, int inorder_left, int inorder_right, int postorder_left, int postorder_right) {
        if (postorder_left > postorder_right) return null;
        // 找到根节点在中序遍历的位置
        int inorder_root = map.get(postorder[postorder_right]);
        // 创建根节点用于返回，根的值为原二叉树的根节点值
        TreeNode root = new TreeNode(postorder[postorder_right]);
        // 剩余左子树的长度，用于确认接下来要传入的参数的值
        int leftTreeSize = inorder_root - inorder_left;
        // 看图说话，分别需要左子树（蓝色），就传入需要的前序和中序的范围，右子树（未标色）同理
        root.left = build(inorder, postorder, inorder_left, inorder_root - 1, postorder_left, postorder_left + leftTreeSize - 1);
        root.right = build(inorder, postorder, inorder_root + 1, inorder_right, postorder_left + leftTreeSize, postorder_right - 1);
        return root;
    }


}