1、重建二叉樹(shù)：
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回。
2、樹(shù)的子結(jié)構(gòu)：
輸入兩棵二叉樹(shù)A和B，判斷B是不是A的子結(jié)構(gòu)。如圖：A中有一部分子樹(shù)的結(jié)構(gòu)和B是一樣的，因此B是A的子結(jié)構(gòu)
#include<stdio.h>
using namespace std;
struct Node
{
int value;//根節(jié)點(diǎn)
BinaryTreeNode* m_pLeft;//左孩子
BinaryTreeNode* m_pRight;//右孩子
}
//判斷二叉樹(shù)A是否包含二叉樹(shù)B
//1->A;2->B
bool DoseTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
//如果二叉樹(shù)B節(jié)點(diǎn)全部遍歷完，返回false
if(pRoot2 == NULL)
return false;
//如果遍歷完二叉樹(shù)A的全部結(jié)點(diǎn)，并且二叉樹(shù)2未遍歷結(jié)束，返回false
if(pRoot1 == NULL)
return false;
//如果遍歷過(guò)程中有二叉樹(shù)的結(jié)點(diǎn)不相同，遍歷結(jié)束，返回false
if(pRoot1->value != pRoot2->value)
return false;
//遞歸遍歷二叉樹(shù)的所有左右子樹(shù)
return DoseTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft)&&
DoseTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}
//判斷兩棵樹(shù)的根結(jié)點(diǎn)是否相同
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
bool result = false;
if(pRoot1 != NULL && pRoot2 != NULL)
{
//如果兩個(gè)根節(jié)點(diǎn)相同，就是找到了
if(pRoot1 ->value == pRoot2 ->value)
result = DoseTree1HaveTree2(pRoot1,pRoot2);
//如果未找到，則從左子樹(shù)開(kāi)始尋找
if(!result)
return = HasSubtree(pRoot1->m_pRight,pRoot2);
//如果未找到，從右子樹(shù)中查找
if (!result)
result = HasSubtree(pRoot1->m_pRight, pRoot2);
}
return result;
}3、二叉樹(shù)的鏡像
請(qǐng)完成一個(gè)函數(shù)，輸入一個(gè)二叉樹(shù)，該函數(shù)輸出它的鏡像。如圖，右邊的二叉樹(shù)就是左邊的樹(shù)的鏡像。
#include <iostream>
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
// 生成二叉樹(shù)鏡像
void MirrorRecursively (BinaryTreeNode *pNode)
{
// 如果結(jié)點(diǎn)為空，停止遞歸
if (pNode == nullptr)
return;
// 交換左右子樹(shù)
std::swap(pNode->m_pLeft,pNode->m_pRight);
// 當(dāng)左子樹(shù)非空時(shí)，遞歸生成左子樹(shù)鏡像
if (pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);
// 當(dāng)右子樹(shù)非空時(shí)，遞歸生成右子樹(shù)鏡像
if (pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}
int main()
{
return EXIT_SUCCESS;
}
4、從上往下打印二叉樹(shù)
從上往下打印出二叉樹(shù)的每個(gè)結(jié)點(diǎn)，同一層的結(jié)點(diǎn)按照從左到右的順序打印。
#include <iostream>
#include <queue>
using namespace std;
struct BinaryTreeNode
{
int value;
BinaryTreeNode*m_pLeft;
BinaryTreeNode*m_pRight;
};
//從上往下打印
void PrintTree(BinaryTreeNode *pTreeRoot)
{
if(pTreeRoot != NULL)
return;
queue<BinaryTreeNode *> queNode;
queNode.push(pTreeRoot);
while (!queNode.empty())
{
BinaryTreeNode *pNode =queNode.front();
queNode.pop();
cout << pNode->value << " ";
if (pNode->p_left)
queNode.push(pNode->p_left);
if (pNode->p_right)
queNode.push(pNode->p_right);
}
}
int main()
{
queue<BinaryTreeNode>data;
BinaryTreeNode n1{5, nullptr, nullptr};
BinaryTreeNode n2{7, nullptr, nullptr};
BinaryTreeNode n3{9, nullptr, nullptr};
BinaryTreeNode n4{11, nullptr, nullptr};
BinaryTreeNode n5{6, &n1, &n2};
BinaryTreeNode n6{10, &n3, &n4};
BinaryTreeNode n7{8, &n5, &n6};
PrintTree(&n7);
return EXIT_SUCCESS;
}5、二叉搜索樹(shù)的后序遍歷序列
輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同
#include <iostream>
#include <queue>
using namespace std;
bool VerifySequenceOfBST(int sequence[], int length)
{
if(sequence == NULL || length <= 0)
return false;
int root = length - 1;
int i = 0;
for(;i<length-1;++i)
{
if(sequence[i] > root)
break;
}
int j = i;
for(;j<length-1;++j)
{
if(sequence[j] < root)
return false;
}
//只有當(dāng)兩個(gè)結(jié)點(diǎn)都為真才可以
bool left = true;
if (i > 0)
left = VerifySequenceOfBST(sequence, i);
bool right = true;
if (i < length - 1)
right = VerifySequenceOfBST(sequence + i, length - i - 1);
return (left && right);
}
int main()
{
int binary_sort_tree[] = {5,7,6,9,11,10,8};
cout << "The result is "
<< VerifySequenceOfBST(binary_sort_tree, sizeof(binary_sort_tree)/ sizeof(int)) << endl;
return EXIT_SUCCESS;
}6、二叉樹(shù)中和為某一值的路徑
class Soultion
{
puclic:
vector<vector<int>>result;
vector<int>tmp;
vector<vector<int> > FindPath(TreeNode* root,int sum)
{
if(root == NULL)
return NULL;
tmp.push_back(root->val);
if(root->left == NULL && root->right && sum->root->val ==0)
result.push_back(tmp);
//如果不是父節(jié)點(diǎn)就是子節(jié)點(diǎn)
FindPath(root->left,sum->root->val);
FindPath(root->right,sum->root->val);
if(tmp.size()>0)
temp.pop_back();
return result;
}
};
7、二叉搜索樹(shù)與雙向鏈表
8、二叉樹(shù)的深度
輸入一棵二叉樹(shù)的根結(jié)點(diǎn)，求該樹(shù)的深度
思路：如果一棵樹(shù)只有一個(gè)結(jié)點(diǎn)，它的深度為1。如果根結(jié)點(diǎn)只有左子樹(shù)，那么樹(shù)的深度應(yīng)該是該其左子樹(shù)的深度加1;同樣如果根結(jié)點(diǎn)只有右子樹(shù)而沒(méi)有左子樹(shù)，那么樹(shù)的深度是其右子樹(shù)的深度加1。如果既有右子樹(shù)又有左子樹(shù)，那該樹(shù)的深度就是其左、右子樹(shù)的深度較大值再加1。
頭文件：
#include <iostream>
using namespace std;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};算法內(nèi)容：
int TreeDepth(BinaryTreeNode* pRoot)
{
if(pRoot == NULL)
return;
int nLeft = TreeDepth(pRoot->m_pLeft);
int nRight = TreeDepth(pRoot->m_pRight);
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}主函數(shù)：
int main()
{
BinaryTreeNode n8{8, nullptr, nullptr};
BinaryTreeNode n7{7, nullptr, nullptr};
BinaryTreeNode n6{6, nullptr, nullptr};
BinaryTreeNode n5{5, nullptr, nullptr};
BinaryTreeNode n4{4, &n8, nullptr};
BinaryTreeNode n3{3, &n6, &n7};
BinaryTreeNode n2{2, &n4, &n5};
BinaryTreeNode n1{1, &n2, &n3};
int depth = 0;
cout << "The depth is: " << TreeDepth(&n1) << endl
<< "Is a Balance Tree ? : " << IsBalanced(&n1, &depth) << endl;
return 0;
}
9、平衡二叉樹(shù)
題目：輸入一棵二叉樹(shù)，判斷該二叉樹(shù)是否是平衡二叉樹(shù)
思想：如果某二叉樹(shù)中任意節(jié)點(diǎn)的左右子樹(shù)的深度相差不超過(guò)1，那么它就是一棵平衡二叉樹(shù)。
class Solution
{
public:
bool IsBalanced_Solution(TreeNode* pRoot)
{
if(pRoot == NULL)
return true;
int depth = 0;
return IsBalanced(pRoot, &depth);
}
private:
bool IsBalanced(TreeNode *pRoot, int *depth)
{
if(pRoot == NULL)
{
*depth =0;
return true;
}
int left,right;
if(IsBalanced(pRoot->left, &left) && IsBalanced(pRoot->right, &right))
{
int diff = left - right;
if(diff <= 1 && diff >= -1)
{
*depth = left>right?(left+1):(right+1);
return true;
}
}
return false;
}
};10、二叉樹(shù)的下一個(gè)結(jié)點(diǎn)
*/
/*分析二叉樹(shù)的下一個(gè)節(jié)點(diǎn)，一共有以下情況：
1.二叉樹(shù)為空，則返回空；
2.節(jié)點(diǎn)右孩子存在，則設(shè)置一個(gè)指針從該節(jié)點(diǎn)的右孩子出發(fā)，一直沿著指向左子結(jié)點(diǎn)的指針找到的葉子節(jié)點(diǎn)即為下一個(gè)節(jié)點(diǎn)；
3.節(jié)點(diǎn)不是根節(jié)點(diǎn)。如果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子，則返回父節(jié)點(diǎn)；否則繼續(xù)向上遍歷其父節(jié)點(diǎn)的父節(jié)點(diǎn)，重復(fù)之前的判斷，返回結(jié)果*/
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==NULL)
return NULL;
if(pNode->right!=NULL){
pNode = pNode->right;
while(pNode->left){
pNode = pNode->left;
}
return pNode;
}
while(pNode->next!=NULL){
TreeLinkNode* proot = pNode->next;
if(proot->left == pNode)
return proot;
pNode=pNode->next;
}
return NULL;
}
};11、對(duì)稱的二叉樹(shù)
題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱的。注意，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的，定義其為對(duì)稱的
思路：遞歸判斷：R1->left與R2->right比較，R2->left與R1->right比較文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-410915.html
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
class Solution
{
public:
bool isSymmetrical(TreeNode* pRoot)
{
return isSymmetrical(pRoot,pRoot);
}
private:
bool isSymmetrical(TreeNode *pRoot1, TreeNode *pRoot2)
{
if(pRoot1 == NULL && pRoot2 == NULL)
{
return true;
}
if(pRoot1 == NULL || pRoot2 == NULL)
{
return false;
}
if(pRoot1->val != pRoot2->val)
{
return false;
}
return isSymmetrical(pRoot->left, &right) && isSymmetrical(pRoot->right,&left);
}
};12、按之字形順序打印二叉樹(shù)
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-410915.html
13、把二叉樹(shù)打印成多行
struct TreeNode
{
int val;
struct TreeNode*left;
struct TreeNode*right;
TreeNode(int x):val(x),left(NULL),right(NULL);
{}
};
class Solution
{
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>>ans;
if(pRoot == NULL)
return ans;
queue<TreeNode*>q;
q.push(pRoot);
while(q.empty())
{
int size = q.size();//讀取每一層的元素的數(shù)量
vector<TreeNode*>q1;
while(size--)
{
TreeNode*front = q.front();
q.pop();
q1.push_back(front ->val);
if(front->left!=NULL) return front->left;
if(front->right!=NULL) return front->right;
}
ans.push_back(q1);
}
return ans;
}
};14、序列化二叉樹(shù)
15、二叉搜索樹(shù)的第k個(gè)結(jié)點(diǎn)
//中序遍歷
TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
{
TreeNode *cur = root;
int count = 0;
stack<TreeNode*>s;
while(s.empty() || cur)
{
if(cur != NULL)
{
s.push(cur);
cur = cur->left;
}
else
{
cur = s.top();
s.pop();
count++;
if(num == k)
return cur->val;
cur = cur->right;
}
}
return 0;
}?
到了這里，關(guān)于劍指offer：關(guān)于二叉樹(shù)的匯總（c++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
