面试题7-重建二叉树

悠悠 2022-03-10 02:54 222阅读 0赞

# 一、题目 #

### **       题目：**输入某二叉树的前序遍历[和中][Link 1]序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。 ###

# 二、题目分析 #

###        二叉树的前序遍历顺序是：先访问根节点，然后前序遍历左子树，再前序遍历右子树。 ###

###        中序遍历顺序是：中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。 ###

###        1、二叉树的前序遍历序列一定是该树的根节点 ###

###        2、中序遍历序列中根节点前面一定是该树的左子树，后面是该树的右子树 ###

###       从上面可知，题目中前序遍历的第一个节点\{1\}一定是这棵二叉树的根节点，根据中序遍历序列，可以发现中序遍历序列中节点\{1\}之前的\{4,7,2\}是这棵二叉树的左子树，\{5,3,8,6\}是这棵二叉树的右子树。然后，对于左子树，递归地把前序子序列\{2,4,7\}和中序子序列\{4,7,2\}看成新的前序遍历和中序遍历序列。此时，对于这两个序列，该子树的根节点是\{2\}，该子树的左子树为\{4,7\}、右子树为空，如此递归下去（即把当前子树当做树，又根据上述步骤分析）。\{5,3,8,6\}这棵右子树的分析也是这样。 ###

# 三、代码实现 #

BinaryTreeNode* construct(int* preorder, int* inorder, int lenght) {//前序数组、中序数组和数组长度
    	if (preorder == nullptr || inorder == nullptr || lenght <= 0) {//判读前序和后序是否为空
    		return nullptr;
    	}
    	return constructCore(preorder,inorder,lenght);
    }
    BinaryTreeNode* constructCore(int* preorder, int* inorder, int lenght) {//前序、中序和序列长度
    	if (lenght <= 0) {//若序列长度小于等于0，则返回nullptr
    		return nullptr;
    	}
    	int rootValue = preorder[0];//确认根节点的值为前序的第一个元素
    	BinaryTreeNode* root = new BinaryTreeNode();//创建根结点
    	root->value = rootValue;
    	root->left = root->right = nullptr;
    	if (lenght == 1) {//若序列长度为1，则直接返回根节点
    		return root;
    	}
    	int len1, len2;//定义左子树的序列长度和右子树的序列长度
    	for (int i = 0; i < lenght; ++i) {//循环查找根结点在中序遍历中的位置
    		if (rootValue == inorder[i]) {
    			len1 = i;
    			break;
    		}
    	}
    	len2 = lenght - len1 - 1;
    	if (len1 > 0 ) {//左子树的序列长度大于0
    		int* left_preorder = new int[len1];//创建左子树的前序序列
    		int* left_inorder = new int[len1];//创建左子树的中序序列
    		for (int i = 0; i < len1; ++i) {
    			left_preorder[i] = preorder[i + 1];
    			left_inorder[i] = inorder[i];		
    		}
    		root->left = constructCore(left_preorder, left_inorder, len1);//采用递归，深入左子树
    	}
    	if (len2 > 0) {//右子树的序列长度大于0
    		int* right_preorder = new int[len2];//创建右子树的前序序列
    		int* right_inorder = new int[len2];//创建右子树的中序序列
    		for (int i = 0; i < len2; ++i) {
    			right_preorder[i] = preorder[i + 1 + len1];
    			right_inorder[i] = inorder[i + 1 + len1];
    		}
    		root->right = constructCore(right_preorder, right_inorder, len2);//采用递归，深入右子树
    	}
    	return root;//返回根结点
    }

/**
         * 
         * @param pre  前序遍历
         * @param in    中序遍历
         * @return        二叉树根节点
         */
         BinaryTreeNode* reConstructBinaryTree(int* pre,int* in,int length) {
             /*
              * 输入合法性判断， 不能为空，先序和后序长度要一致
              */
             if(pre == null || in == null || length <= 0) 
                 return null;
             
             return construct(pre, 0, length-1, in, 0, length-1);
         }
         /**
          * 
          * @param pre    前序遍历
          * @param ps    前序遍历的开始位置
          * @param pe    前序遍历的结束位置
          * @param in    中序遍历
          * @param is    中序遍历的开始位置
          * @param ie    中序遍历的结束位置
          * @return        数的根节点
          */
         BinaryTreeNode* construct(int* pre, int ps, int pe, int* in, int is, int ie) {
             if(ps > pe) return null;
             
             // 取前序遍历的第一个数字就是根节点
             int value = pre[ps];
             // 在中序遍历中中寻找根节点
             int index =is;
             while(index <= ie && value != in[index]) {
                 index ++;
             }
             // 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常 
             if(index > ie) 
                 throw "error";
             
             // 创建当前根节点，并为根节点赋值
             BinaryTreeNode* node = new BinaryTreeNode();
             node->data = value;
             // 递归调用构建当前节点的左子树 
             node->left = construct(pre, ps+1, ps+index-is, in, is, index-1);
             // 递归调用构建当前节点的右子树
             node->right = construct(pre, ps+index-is+1, pe, in, index+1, ie);
             
             return node;
        }

[Link 1]: https://www.baidu.com/s?wd=%E5%92%8C%E4%B8%AD&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd