剑指offer2-重建二叉树

本文主要是介绍剑指offer2-重建二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的遍历：
先序遍历：先访问根节点，再访问左子树，最后访问右子树；
中序遍历：先访问左子树，再访问根节点，最后访问右子树；
后序遍历：先访问左子数，再访问右子树，最后访问根节点；
一般给定一棵二叉树的中序遍历和先序遍历或者给定一个二叉树的中序遍历和后序遍历，这棵二叉树就可以确定下来。仅仅给定先序遍历和后序遍历是无法确定的。
题目：
给定某二叉树的先序和中序遍历结果，请确定该二叉树：

#include<iostream>
using namespace std;
struct TreeNode
{int value;TreeNode* leftTree;TreeNode* rightTree;
};
TreeNode* constructCore(int* startPreOrder, int* endPreOrder, int* startInOrder,int* endInOrder)
{int rootValue = startPreOrder[0];TreeNode* root = new TreeNode;root->value = rootValue;root->leftTree = root->rightTree = NULL;if (startPreOrder == endPreOrder){if (startInOrder == endInOrder && *startPreOrder == *endPreOrder){return root;//只有一个元素时}else{throw exception("Invalid input.");}}int* rootInOrder = startInOrder;while (rootInOrder <= endInOrder && *rootInOrder != rootValue){rootInOrder++;}if (rootInOrder == endInOrder && *rootInOrder != rootValue){throw exception("Invalid inout.");}int leftLength = rootInOrder - startInOrder;int rightLength = endPreOrder - startPreOrder - leftLength;if (leftLength > 0){//构建左子树root->leftTree = constructCore(startPreOrder + 1, startPreOrder + leftLength,startInOrder, rootInOrder - 1);}if (rightLength > 0){root->rightTree = constructCore(startPreOrder + leftLength + 1, endPreOrder,rootInOrder + 1, endInOrder);}return root;
}
TreeNode* construct(int* preOrder, int* inOrder, int length)
{if (preOrder == NULL || inOrder == NULL || length <= 0){return NULL;}return constructCore(preOrder, preOrder + length - 1, inOrder,inOrder + length - 1);
}
void printInOrder(TreeNode* root)
{if (root->leftTree != NULL){printInOrder(root->leftTree);}cout << root->value << " ";if (root->rightTree != NULL){printInOrder(root->rightTree);}
}
void printPreOrder(TreeNode* root)
{cout << root->value << " ";if (root->leftTree != NULL){printPreOrder(root->leftTree);}if (root->rightTree != NULL){printPreOrder(root->rightTree);}
}
void printPosterOrder(TreeNode* root)
{if (root->leftTree != NULL){printPosterOrder(root->leftTree);}if (root->rightTree != NULL){printPosterOrder(root->rightTree);}cout << root->value << " ";
}
int main()
{int preOrder[] = {1, 2, 4, 7, 3, 5, 6, 8};int inOrder[] = {4, 7, 2, 1, 5, 3, 8, 6};int length = sizeof(preOrder) / sizeof(int);TreeNode* root = construct(preOrder, inOrder, length);cout << "中序遍历：" << endl;printInOrder(root);cout << endl;cout << "先序遍历" << endl;printPreOrder(root);cout << endl;cout << "后序遍历" << endl;printPosterOrder(root);cout << endl;return 0;
}

这篇关于剑指offer2-重建二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---