剑指offer：重建二叉树（根据前序遍历和中序遍历结果）

ゝ一纸荒年。 2022-11-12 02:33 112阅读 0赞

![转自leetcode剑指offer][leetcode_offer]根据前序遍历和中序遍历的结果构造二叉树，思路（leetcode上有图文详解）：由前序遍历结果得到根节点的数值，再在中序遍历结果中查找该数值的位置，该位置左边的为这个根节点的左子树，右边的为右子树，故而可得这个根节点左右子树的长度，再到前序遍历中，由这个长度可将前序遍历结果分成三部分，分别是根节点、左子树、右子树，左子树根节点和右子树根节点皆为该子树第一个元素，所以可得到根、左、右结点，再对左右子树进行相同操作，最终递归得出完整的二叉树。  
代码如下：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        //先定义一个preorder，防止递归一直重复传递
        private int[] preorder;
        //存储中序遍历结点值和对应的下标位置
        private Map<Integer,Integer> inMap;
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
            this.preorder=preorder;
            inMap=new HashMap<Integer,Integer>();
            int n=inorder.length;
            //给map赋值
            for(int i=0;i<n;i++){ 
                inMap.put(inorder[i],i);
            }
            return build(0,n-1,0,n-1);
        }
        public TreeNode build(int pre_left,int pre_right,int in_left,int in_right){ 
        	//若左结点下标大于右结点下标，则不存在子树，返回null
            if(pre_left>pre_right) return null;
            //建立根结点
            TreeNode root=new TreeNode(preorder[pre_left]);
            //找到根节点在中序遍历序列的对应位置
            int in_root_index=inMap.get(preorder[pre_left]);
            //求出左子树的结点个数
            int length=in_root_index-in_left;
            root.left=build(pre_left+1,pre_left+length,in_left,in_root_index-1);
            root.right=build(pre_left+length+1,pre_right,in_root_index+1,in_right);
            return root; 
        }
    }

[leetcode_offer]: /images/20221022/599d93016f9a49aa83f1df712e2bc445.png