从前序遍历与中序遍历序列构造二叉树

桃扇骨 2023-09-30 09:47 19阅读 0赞

我们可以知道 中序遍历时先遍历完左子树 再遍历根结点最后遍历右子树，前序遍历是先遍历根结点再遍历左子树，最后遍历右子树，综上可知，前序遍历的(根+左子树)个数 = 中序遍历的(左子树+根)个数。利用这个性质，可知下边的:

对于前序遍历（根左右）

设前序遍历出的数组开始下标为preLeft，结束为preRight

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:67px;">根</td> 
   <td style="width:215px;">左子树</td> 
   <td style="width:216px;">右子树</td> 
  </tr> 
  <tr> 
   <td style="width:67px;">preLeft</td> 
   <td style="width:215px;">[preLeft+1,pIndex-inLeft+preLeft]</td> 
   <td style="width:216px;">[pIndex-inLeft+preLeft+1,preRight]</td> 
  </tr> 
 </tbody> 
</table>

对于中序遍历（左根右）

设中序遍历出数组开始下标为inLeft,结束下标为inRight

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:173px;">左子树</td> 
   <td style="width:109px;">根</td> 
   <td style="width:216px;">右子树</td> 
  </tr> 
  <tr> 
   <td style="width:173px;">[inLeft-pIndex-1]</td> 
   <td style="width:109px;">pIndex</td> 
   <td style="width:216px;">[pIndex+1,inRight]</td> 
  </tr> 
 </tbody> 
</table>

代码：

class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            int preLen = preorder.length;
            int vinLen = inorder.length;
            if(preLen!=vinLen) return null;
            Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<vinLen;i++){
                map.put(inorder[i],i);
            }
            return buildTree(map,preorder,inorder,0,preLen-1,0,vinLen-1);
        }
        public TreeNode buildTree(Map<Integer,Integer> map,int[] preorder,int[] inorder,int preLeft,int preRight,int vinLeft,int vinRight){
            if(preLeft>preRight || vinLeft>vinRight) return null;
            int rootVal = preorder[preLeft];
            int pIndex =  map.get(rootVal);
            TreeNode root = new TreeNode(rootVal);
            root.left = buildTree(map,preorder,inorder,preLeft+1,pIndex-vinLeft+preLeft,vinLeft,pIndex-1);
            root.right = buildTree(map,preorder,inorder,pIndex-vinLeft+preLeft+1,preRight,pIndex+1,vinRight);
            return root;
        }
    }