@kakadee
2016-06-04T06:37:46.000000Z
字数 7227
阅读 1103
编程
算法
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
TreeNode* buildHelper(vector<int> &pre,vector<int> &in,int startPre,int endPre,int startIn,int endIn)
{
if (startPre > endPre || startIn > endIn) return NULL;
TreeNode *root = new TreeNode(pre[startPre]);
for(int i = startIn; i <= endIn; ++i)
{
if(in[i] == root->val)
{
root->left = buildHelper(pre,in,startPre+1,startPre+i-startIn,startIn,i-1);
root->right = buildHelper(pre,in,startPre+i-startIn+1,endPre,i+1,endIn);
}
}
return root;
}
根据字符串创建二叉树,和根据二叉树重建字符串。
string Serialize(TreeNode *root) {
string ans;
if (root == NULL) return &ans[0];
queue<TreeNode *> Q;
Q.push(root);
while (!Q.empty()) {
TreeNode *node = Q.front();
Q.pop();
if (node == NULL) ans += ",#";
else {
Q.push(node->left);
Q.push(node->right);
string tmp = to_string(node->val);
ans += "," + tmp;
}
}
return ans.substr(1);
}
TreeNode* Deserialize(char *str) {
string s = str;
if (s.size() == 0) return NULL;
vector<TreeNode*> path;
while (s != "") {
int i = 0;
while (i < s.size() && s[i] != ',') i++;
string tmp = s.substr(0, i);
if (tmp == "#") {
TreeNode* p = NULL;
path.push_back(p);
}
else {
int val = atoi(tmp.c_str());
TreeNode* p = new TreeNode(val);
path.push_back(p);
}
if (i >= s.size() - 1) s = "";
else s = s.substr(i + 1);
}
int index = 1, i = 0;
while (index < path.size()) {
if (path[i] != NULL) {
if (index < path.size()) path[i]->left = path[index++];
if (index < path.size()) path[i]->right = path[index++];
}
i++;
}
return path[0];
}
class Solution {
public:
int TreeDepth(TreeNode* pRoot) {
if(pRoot == NULL) return 0;
int left = TreeDepth(pRoot->left);
int right = TreeDepth(pRoot->right);
return max(left,right)+1;
}
};
任意节点的左右子树深度相差不超过1。
判断一颗二叉树是不是平衡二叉树。
//后续遍历二叉树,遍历过程中求子树高度,判断是否平衡
bool isBalanced(TreeNode* root,int &depth){
if(root == NULL)
return true;
int left = 0,right = 0;
if(isBalanced(root->left,left) && isBalanced(root->right,right)){
int dif = left - right;
if(dif > 1 || dif < -1) return false;
depth = max(left,right)+1;
return true;
}
else
return false;
}
bool IsBalanced_Solution(TreeNode* pRoot){
int depth = 0;
return isBalanced(pRoot,depth);
}
二叉树的镜像定义:
源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
操作给定的二叉树,将其变换为源二叉树的镜像。
void Mirror(TreeNode *pRoot){
if(pRoot == NULL)
return;
TreeNode* tmp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = tmp;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
判断一颗二叉树是不是对称的。
bool cmpRoot(TreeNode* left,TreeNode* right){
if(left == NULL && right == NULL)
return true;
if((!left && right) || (!right && left))
return false;
if(left->val != right->val)
return false;
return cmpRoot(left->right,right->left) && cmpRoot(left->left,right->right);
}
bool isSymmetrical(TreeNode* pRoot){
if(pRoot == NULL) return true;
return cmpRoot(pRoot->left,pRoot->right);
}
输入两颗二叉树A,B,判断B是不是A的子结构。
(空树不属于任何一个树的子结构)
bool isSubtree(TreeNode* pRootA, TreeNode* pRootB){
if(pRootB == NULL) return true;
if(pRootA == NULL) return false;
if(pRootA->val == pRootB->val)
return isSubtree(pRootA->left,pRootB->left) && isSubtree(pRootA->right,pRootB->right);
else
return false;
}
bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB){
if(pRootA == NULL) return false;
return isSubtree(pRootA,pRootB) || HasSubtree(pRootA->left,pRootB) || HasSubtree(pRootA->right,pRootB);
}
TreeNode* Convert(TreeNode* root)
{
if (root == NULL || (!root->left && !root->right))
{
return root;
}
// 先返回左子树双向链表的表头
TreeNode *left = Convert(root->left);
if (!left){
TreeNode *p = left;
while(p && p->right){
p = p->right;
}
root->left = p;
p->right = root;
}
// 再返回右子树双向链表的表头
TreeNode *right = Convert(root->right);
if (right) {
root->right = p;
p->left = root;
}
return left == NULL ? root:left;
}
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
// 1. 如果此节点有右子树,返回右子树的最左节点
// 2. 否则,如果该节点是父节点的左孩子,返回其父节点;
// 3. 否则,向上找到有左孩子的父节点,返回该父节点。
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(!pNode) return NULL;
if (pNode->right)
{
TreeLinkNode* p = pNode->right;
while (p && p->left)
{
p = p->left;
}
return p;
}
while (pNode->next) {
if(pNode->next->left == pNode)
return pNode->next;
pNode = pNode->next;
}
return NULL;
}
string post;
void postprint(string pre,string in) {
if(pre.size() == 0) return;
int pos = in.find(pre[0]);
postprint(pre.substr(1,pos),in.substr(0,pos));
postprint(pre.substr(pos+1),in.substr(pos+1));
post.push_back(pre[0]);
}
vector<int> PrintFromTopToBottom(TreeNode *root) {
vector<int> ans;
if (root == NULL) return ans;
queue<TreeNode *> Q;
Q.push(root);
while(!Q.empty()) {
TreeNode *node = Q.front();
Q.pop();
if(node->left) Q.push(node->left);
if(node->right) Q.push(node->right);
ans.push_back(node->val);
}
return ans;
}
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
vector<vector<int> > Print(TreeNode* root) {
vector<vector<int>> ans;
if(root == NULL) return ans;
vector<int> tmp; //存储每一个层的值
queue<TreeNode *> Q;
queue<int> level;
int curlevel = 0;
Q.push(root);
level.push(0);
while(!Q.empty()){
//如果现在队列顶端的节点level值大于curlevel,证明已经进入到下一层,所以更新curlevel到现在的层
if(level.front()>curlevel){
curlevel=level.front();
ans.push_back(tmp);
tmp.clear();
}
TreeNode *node = Q.front();
Q.pop();
level.pop();
//每一次将当前节点放入tmp中,并将他的子节点放入队列,等待之后的遍历,子节点所在的level层数加一,同时放入队列
tmp.push_back(node->val);
if(node->left){
Q.push(node->left);
level.push(curlevel+1);
}
if(node->right){
Q.push(node->right);
level.push(curlevel+1);
}
}
//由于最后一次Q为空,所以最后一层存储在tmp里的值并没有放入ans中,所以得再放置一次
ans.push_back(tmp);
return ans;
}
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
vector<vector<int> > Printz(TreeNode* root)
{
vector< vector<int> > ans;
if (root == NULL) return ans;
queue<TreeNode *> Q;
queue<int> level;
vector<int> tmp;
int curLevel = 0;
Q.push(root);
level.push(0);
while(!Q.empty()) {
if(level.front() > curLevel){
if(curLevel & 1) // 如果是奇数层,翻转
reverse(tmp.begin(),tmp.end());
ans.push_back(tmp);
tmp.clear();
curLevel = level.front();
}
TreeNode *node = Q.front();
Q.pop();
level.pop();
tmp.push_back(node->val);
if(node->left){
Q.push(node->left);
level.push(curLevel+1);
}
if(node->right){
Q.push(node->right);
level.push(curLevel+1);
}
}
if(curLevel & 1)
reverse(tmp.begin(),tmp.end());
ans.push_back(tmp);
return ans;
}
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
//BST的后序序列的合法序列是,对于一个序列S,最后一个元素是x (也就是根),如果去掉最后一个元素的序列为T,那么T满足:T可以分成两段,前一段(左子树)小于x,后一段(右子树)大于x,且这两段(子树)都是合法的后序序列。
bool judge(vector<int>& a, int left, int right) {
if (left >= right) return true;
int i = left;
// 这一句特别重要,如果不判断右子树是否比根大,那么【7,4,6,5】就会错误判断
while (i < right && a[i] < a[right]) i++;
for (int j = i; j < right; j++)
if (a[j] < a[right]) return false;
return judge(a, left, i - 1) && judge(i, right - 1);
}
bool VerifySquenceOfBST(vector<int> a) {
if (!a.size()) return false;
return judge(a, 0, a.size() - 1);
}
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
class Solution {
public:
vector<vector<int> > ans;
vector<int> path;
void helper1(TreeNode* root, int target) { // 从根节点到叶子节点和为target的路径
path.push_back(root->val);
if (target - root->val == 0 && !root->left && !root->right) {
ans.push_back(path); // 此处不应该有return,如果return 那么path.pop_back()将不执行
}
if (root->left) helper1(root->left, target - root->val);
if (root->right) helper1(root->right, target - root->val);
path.pop_back();
}
void helper2(TreeNode* root, int target) { // 从根节点到任意节点和为target的路径
path.push_back(root->val);
if (target - root->val == 0) {
ans.push_back(path);
}
if (root->left) helper2(root->left, target - root->val);
if (root->right) helper2(root->right, target - root->val);
path.pop_back();
}
void helper3(TreeNode* root, int target) { // 任意父节点到子节点和为target的路径
helper2(root, target);
if (root->left) helper3(root->left, target);
if (root->right) helper3(root->right, target);
}
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
if (root == NULL) return ans;
helper1(root, expectNumber);
return ans;
}
};