重建二叉树

灰太狼 2022-04-03 13:44 264阅读 0赞

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
     */
    class Solution {
        
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        
            int n = pre.size(),m = vin.size();
            if(n!=m) return NULL;
            return helper(pre,vin,0,n-1,0,0,n-1);
        }
        
        TreeNode* helper(vector<int>& pre, vector<int>& vin,int l1,int r1,int root_index,int l2,int r2) {
        
            //如果传入的根的位置并不在给定的前序遍历的数组的范围内那么就说明该子树不存在 返回空
            if(root_index<l1||root_index>r1) return NULL;
            int root = pre[root_index];
            
            int ind = 0;
            //找到根在中序数组当中的位置
            for(int i=l2;i<=r2;++i) {
        
                if(vin[i]==root) {
        
                    ind = i;
                    break;
                }
            }
            TreeNode* rt = new TreeNode(root);
            //得到理论上左右子树的根结点的位置
            int left = root_index + 1;//左子树的根是前序遍历当中当前根的下一个就是
            int right = root_index + ind - l2 + 1;//前序遍历当中右子树的根是根往右偏移整个左子树的结点个数
            //计算左右子树在遍历数组当中各自的位置边界 
            rt->left = helper(pre,vin,l1+1,l1+ind-l2,left,l2,ind-1);
            rt->right = helper(pre,vin,l1+ind-l2+1,r1,right,ind+1,r2);
            return rt;
        }
    };

#### 就是通过前序和中序重建二叉树 ####

简直写的我难受，反正思路就是很简单就是coding的问题，一些边界扣的难受。  
细节的描述在代码当中。  
总结来说就是使用递归的方式去构建二叉树，先生成根节点在递归的生成左右子树的根节点再和根连上。  
给的参数是数组，所以必须规定好递归过程当中的每个数组的边界，还需要指定在前序遍历的数组当中当前根所在的位置，通过根的值可以在中序遍历当中找到根的位置，然后通过边界个根的位置能够得出左右子树结点的个数，再通过这个长度关系可以在前序遍历当中结合当前根的位置计算出下一步当中的左子树的根和右子树的根的位置，计算方式：  
前序遍历当中根的下一个就是其左孩子，跳过左子树的长度的位置就是右孩子的位置。  
注意递归的边界当理论的根的位置实际不再计算出的当前前序遍历的边界内的时候说明是不存在这个结点的也就是实际的空节点。