7.【剑指offer】重建二叉树

我会带着你远行 2024-03-26 13:52 56阅读 0赞

[题目][Link 1]

思路：

1.  需要先将中序数组的【值-索引】信息进行储存，接着只要找到前序遍历的结点在中序遍历中的位置，就可以将中序数组分解为左右子树两部分；

1.  根节点在中序数组中的位置为index，进而可求得子树上的结点数 = index - VinS；

1.  创建四个变量来定位子树的位置：前序中的PreS和PreE、中序中的VinS和VinE;

1.  对于叶子结点和子树这两种状态需要分情况进行处理；

1.  时间复杂度：O（N）,N为树的结点数

import java.util.*;
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int[] pre;
        public int[] vin;
        public Map<Integer,Integer> map;
        
        //思路：根据前序数组来定位中序的根结点
        public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
            //初始化
            this.pre = pre;
            this.vin = vin;
            map = new HashMap<>();
            //存储中序数组的位置信息
            for(int i = 0; i < vin.length; i++){
                map.put(vin[i],i);
            }
        
            return getRoot(0,pre.length - 1, 0, vin.length - 1);
        }
    
        //传递的信息：树在两种序列中的位置
        public TreeNode getRoot(int PreS, int PreE, int VinS, int VinE){
            if(PreS > PreE) return null;
            if(VinS > VinE) return null;
            
            //如果是叶子结点
            int rootVal = pre[PreS];
            if(PreS == PreE) return new TreeNode(rootVal);
    
            //如果是子树，先获取根结点
            TreeNode root = new TreeNode(rootVal);
            //只要找到前序遍历的结点在中序遍历中的位置，就可以将中序数组分解为左右子树两部分
            int index = map.get(rootVal);
    
            //左、右子树(index - VinS ：子树的结点个数)
            root.left = getRoot(PreS + 1, PreS + index - VinS, VinS, index - 1);
            root.right = getRoot(PreS + index - VinS + 1, PreE,index + 1,VinE);
    
            return root;
        }
    }

[Link 1]: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=265&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D265&difficulty=&judgeStatus=&tags=&title=&gioEnter=menu