LeetCode Hot 100 No.105 从前序与中序遍历序列构造二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode Hot 100 No.105 从前序与中序遍历序列构造二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1787字，纯文字阅读大概需要3分钟。

内容图文

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

思路：这道题用递归来解决。
首先我们能从一个树的前序遍历序列得知该树的根节点的值。然后我们去中序遍历序列里面找根节点所在位置，那么根节点左右两侧的子序列就是左子树和右子树的中序序列。然后我们再去前序序列里面找，根节点之后紧跟的应该是左子树的前序序列和右子树的前序序列。我们可以通过中序序列知道左子树和右子树的节点数，从而可以得到左子树和右子树的前序序列。
左子树和右子树的前序序列和中序序列得到了之后，就可以投入下一轮递归了。递归函数返回的是一颗树的根节点。终止条件就是当前数的前序和中序序列都只有一个节点，或前序序列和中序序列都为空的情况。

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

    }
}

还有一种优化方法，就是将每次从中序序列中循环查找根节点位置的操作改成从哈希表中查找，时间复杂度为O(1)。

内容总结

以上是互联网集市为您收集整理的LeetCode Hot 100 No.105 从前序与中序遍历序列构造二叉树全部内容，希望文章能够帮你解决LeetCode Hot 100 No.105 从前序与中序遍历序列构造二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---