看完这篇文章，再也不怕面试官问我如何构造二叉树啦！

HelloWorld杰少

发布于 2022-08-04 14:18:34

1360

发布于 2022-08-04 14:18:34

文章被收录于专栏：HelloWorld杰少

1. 根据前序与中序遍历构造二叉树

解题思路：

由于是先序遍历，由此我们可以知道第一个节点为二叉树的根节点。

接下来，我们要做的工作就是找出数组中哪个区间是左子树的区间，哪个是右子树的区间？

题目给出了一个中序遍历数组，由此我们可以通过已知根节点的值，然后遍历中序数组，找到根节点在中序数组中的索引位置 pos。

这样我们就可以知道左子树是在 [0, pos-1] 的区间，右子树是在 [pos+1， len] 的区间。

于是，我们就可以通过递归的方式去构建二叉树，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
  if(preorder.length==0 || inorder.length==0) {
   return null;
  }
  //根据前序数组的第一个元素，就可以确定根节点
  TreeNode root = new TreeNode(preorder[0]);
  for(int i = 0;i < preorder.length; i++) {
   //用preorder[0]去中序数组中查找对应的元素
   if(preorder[0] == inorder[i]) {
    //将前序数组分成左右两半，再将中序数组分成左右两半
    //之后递归的处理前序数组的左边部分和中序数组的左边部分
    //递归处理前序数组右边部分和中序数组右边部分
    int[] pre_left = Arrays.copyOfRange(preorder,1,i+1);
    int[] pre_right = Arrays.copyOfRange(preorder,i+1,preorder.length);
    int[] in_left = Arrays.copyOfRange(inorder,0,i);
    int[] in_right = Arrays.copyOfRange(inorder,i+1,inorder.length);
    root.left = buildTree(pre_left, in_left);
    root.right = buildTree(pre_right, in_right);
    break;
   }
  }
  return root;
 }
}

时间复杂度为: O(n^2) 空间复杂度为: O(n)

优化方案：

上面的思路每次递归构造二叉树的时候，都需要去遍历数组，找出根节点，这样会造成时间复杂度变高。

我们可以通过哈希表来进行优化，将中序数组的节点值与索引值分别作为 key 和 value，存放在哈希表中，这样，我们就不需要每次去遍历中序数组来获得根节点的索引，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public HashMap<Integer, Integer> map = new HashMap();
    int[] preOrder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.preOrder = preorder;

        return helper(0, inorder.length - 1, 0, preOrder.length - 1);
    }

    public TreeNode helper(int inStart, int inEnd, int preStart, int preEnd) {
        if (inStart > inEnd || preStart > preEnd) return null;
        int root = preOrder[preStart]; 
        int pos = map.get(root);
        TreeNode node = new TreeNode(root);
        node.left = helper(inStart, pos - 1, preStart + 1, preStart + pos - inStart);
        node.right = helper(pos + 1, inEnd, preStart + pos - inStart + 1, preEnd);
        return node;
    }
}

时间复杂度为: O(n) 空间复杂度为: O(n)

2. 根据中序与后序遍历构造二叉树

解题思路

由于是后序遍历，由此我们可以知道最后一个节点为二叉树的根节点。

接下来，我们要做的工作就是去找出数组中哪个是左子树的区间和哪个是右子树的区间。

题目由给出了一个中序遍历，由此我们可以通过已知根节点的值，然后遍历中序数组，找到根节点在中序数组中的索引 pos，这样我们就可以知道所有的左子树是在 [0, pos-1] 的区间，右子树是在 [pos+1，len] 的区间。

于是，我们就可以通过递归的方式去构建二叉树，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null){
            return null;
        }
        return dfs(inorder, postorder);
    }

    public TreeNode dfs(int[] inorder, int[] post){
        if(post == null || post.length == 0){
            return null;
        }

        if (post.length == 1){
            return new TreeNode(post[0]);
        }
        
        int n = post.length;
        TreeNode root = new TreeNode(post[n-1]);
        int mid = 0;
        for (int i = 0; i < n; i++) {
            if (post[n-1] == inorder[i]){
                mid = i;
                break;
            }
        }

        int[] in_left = Arrays.copyOfRange(inorder, 0, mid);
        int[] in_right = Arrays.copyOfRange(inorder, mid+1, n);
        int[] post_left = Arrays.copyOfRange(post, 0, mid);
        int[] post_right = Arrays.copyOfRange(post, mid, n-1);

        root.left = dfs(in_left, post_left);
        root.right = dfs(in_right, post_right);

        return root;
    }
}

优化方案：

上述每次递归构造二叉树的时候，都需要去遍历数组，找出根节点，这样会造成时间复杂度变高。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 定义哈希表用于定位中序数组根节点的的位置
    public HashMap<Integer, Integer> map = new HashMap();
    int[] post;

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

        public TreeNode helper(int inStart, int inEnd, int postStart, int postEnd){
        if (inStart > inEnd || postStart > postEnd) return null;
        int val = post[postEnd];
        int rootPos = map.get(val);
        TreeNode node = new TreeNode(val);
        node.left = helper(inStart, rootPos -1 , postStart, postStart + rootPos - inStart -1);
        node.right = helper(rootPos+1, inEnd, postStart + rootPos - inStart, postEnd - 1);
        return node;
    }
}

3. 根据前序和后序遍历构造二叉树

解题思路

首先要做的就是确定左子树的范围，这样我们也就可以确定右子树了。

根据二叉树前序遍历和后序遍历的特性：前序遍历第一个元素是根节点，后面的那一堆就是左子树，接着是右子树，而后序遍历第一个出现的是左子树，然后是右子树，最后才是根节点。

于是，我们可以去遍历后序数组，找到与前序数组 pre[1] 值相等的索引位置 pos，然后，我们就可以知道左子树的区间长度为 leftLen = pos+1, 这样我们就可以确定在后序数组中左子树的范围为 [0, leftLen-1], 右子树的范围为[leftLen, n-2]。

在前序数组中，左子树的范围为 [1, leftLen], 右子树的范围为 [1+leftLen, n-1]。

最后，我们通过递归的方式去构建二叉树，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if(preorder == null || postorder == null){
            return null;
        }
        return dfs(preorder, postorder);
    }

    private TreeNode dfs(int[] pre, int[] post){
        if (pre == null || pre.length == 0){
            return null;
        }
        if(pre.length == 1){
            return new TreeNode(pre[0]);
        }

        // 前序的第一个元素为根节点
        TreeNode root = new TreeNode(pre[0]);
        // 找出左子树区间和右子树区间
        for (int i = 0; i < pre.length; i++) {
            if (pre[1] == post[i]){
                int left_off = i+1;
                // 拆分前序和后序数组，分成4分
                int[] pre_left = Arrays.copyOfRange(pre, 1, left_off+1);
                int[] pre_right = Arrays.copyOfRange(pre, left_off+1, pre.length);
                int[] post_left = Arrays.copyOfRange(post, 0, left_off);
                int[] post_right = Arrays.copyOfRange(post, left_off, pre.length-1);
                // 递归生成二叉树
                root.left = dfs(pre_left, post_left);
                root.right = dfs(pre_right, post_right);
                break;
            }
        }
        return root;
    }
}

最后

好了，关于通过任意三种遍历方式的里俩种去构建二叉树的解题思路就讲解就到这里了，如果大家有更好的思路，可在下方评论留言。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-10-27，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自 HelloWorld杰少微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度