C語言進階二叉樹的基礎與銷毀及層序遍歷詳解
難度簡單
如果二叉樹每個節(jié)點都具有相同的值，那么該二叉樹就是單值二叉樹。
只有給定的樹是單值二叉樹時，才返回true；否則返回false。
示例 1：
輸入：[1,1,1,1,1,null,1]
輸出：true
示例 2：
輸入：[2,2,2,5,2]
輸出：false
提示：
給定樹的節(jié)點數(shù)范圍是[1, 100]。
每個節(jié)點的值都是整數(shù)，范圍為[0, 99]。
解1：
最簡單易懂的解法，先序遍歷一遍，把每個節(jié)點都和那個根節(jié)點的val值相比。最后判斷flag是否為真，若為假，則表明樹中有某節(jié)點的值不符。
其中的return語句是為了避免一些無意義的比較，但是其實第一個if的flag判斷完全可以寫在左遞歸之后，判斷一下，如果左遞歸將flag置為了假，則直接return，不會進入右子樹。如果按照上方解法來說，就是進入右子樹之后，發(fā)現(xiàn)flag為假，再退出。
OJ題里的全局變量需要小心使用，若isUnivalTree里的flag不置為真，則多個測試用例時，可能會承接上一個測試用例假的結果。發(fā)生錯誤。
解法2：
class Solution {
public:
bool isUnivalTree(TreeNode* root) {
if(root == NULL)
return true;
if(root->left != nullptr && root->left->val != root->val)
return false;
if(root->right != nullptr && root->right->val != root->val)
return false;
return isUnivalTree(root->left)
&& isUnivalTree(root->right);
}
};判斷每個結點和其兩個子節(jié)點是否相同，當然，需要確保子節(jié)點非空，若存在不同的，直接返回false，然后遞歸其左右子樹。
其實這個的實質就是前序遍歷，對每個結點的操作就是比較它和兩個子節(jié)點的值是否相同。每個結點如果都和其左右子結點相同，那么這棵樹也就都相同了，如果某處不同，則返回false，層層返回，最終也會返回flase。
解法3：
class Solution {
public:
bool isUnivalTree(TreeNode* root) {
bool ret = PreOrder(root, root->val);
return ret;
}
bool PreOrder(TreeNode* root, int val)
{
if(root == nullptr)
return true;
if(root->val != val)
return false;
return PreOrder(root->left, val)
&& PreOrder(root->right, val);
}
};與2相比沒什么大的改進，只是比較的方式不同而已，仍然是前序遍歷的思想。 第三個return里的&&挺好，左是假則不會對右求值。
難度簡單844
給你兩棵二叉樹的根節(jié)點p和q，編寫一個函數(shù)來檢驗這兩棵樹是否相同。
如果兩個樹在結構上相同，并且節(jié)點具有相同的值，則認為它們是相同的。
示例 1：
輸入：p = [1,2,3], q = [1,2,3]
輸出：true
示例 2：
輸入：p = [1,2], q = [1,null,2]
???????輸出：false
示例 3：
輸入：p = [1,2,1], q = [1,1,2]
???????輸出：false
提示：
- 兩棵樹上的節(jié)點數(shù)目都在范圍
[0, 100]內 -104<= Node.val <= 104
通過次數(shù)344,943提交次數(shù)577,105
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr && q == nullptr)
return true;
if(!(p!=nullptr && q!=nullptr && p->val == q->val))
return false;
bool retl = isSameTree(p->left,q->left);
if(retl == false)
return false;
bool retr = isSameTree(p->right,q->right);
if(retr == false)
return false;
return true;
/*
return isSameTree(p->left,q->left)
&& isSameTree(p->right,q->right);
*/
}
};億億億億億億億億億億舊是前序遍歷,只是兩棵樹同時遍歷而已，判斷是否相同，兩個遞歸和最后那個注釋的是效果相同的。
難度簡單1942
給你一個二叉樹的根節(jié)點root， 檢查它是否軸對稱。
示例 1：
輸入：root = [1,2,2,3,4,4,3]
???????輸出：true
示例 2：
輸入：root = [1,2,2,null,3,null,3]
???????輸出：false
提示：
- 樹中節(jié)點數(shù)目在范圍
[1, 1000]內 -100 <= Node.val <= 100
進階：你可以運用遞歸和迭代兩種方法解決這個問題嗎？
通過次數(shù)603,527提交次數(shù)1,044,923
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return isSame(root->left, root->right);
}
bool isSame(TreeNode* root1, TreeNode* root2)
{
if(root1 == nullptr && root2 == nullptr) // 都是空，結束遞歸，且符合條件
return true;
// 兩者根節(jié)點不相等，結束，不需要進一步判斷了。
if(!(root1 != nullptr && root2 != nullptr && root1->val == root2->val))
return false;
// 進一步判斷
return isSame(root1->left,root2->right) && isSame(root1->right,root2->left);
}
};依舊是前序遍歷。。。。。。。。。
難度簡單739
給你兩棵二叉樹root和subRoot。檢驗root中是否包含和subRoot具有相同結構和節(jié)點值的子樹。如果存在，返回true；否則，返回false。
二叉樹tree的一棵子樹包括tree的某個節(jié)點和這個節(jié)點的所有后代節(jié)點。tree也可以看做它自身的一棵子樹。
示例 1：
輸入：root = [3,4,5,1,2], subRoot = [4,1,2]
???????輸出：true
示例 2：
輸入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
???????輸出：false
提示：
root樹上的節(jié)點數(shù)量范圍是[1, 2000]- ???????
subRoot樹上的節(jié)點數(shù)量范圍是[1, 1000] - ???????
-104<= root.val <= 104 -104<= subRoot.val <= 104
通過次數(shù)125,811提交次數(shù)264,360
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root == nullptr)
return false;
if(isSameTree(root, subRoot);)
return true;
if(isSubtree(root->left,subRoot);)
return true;
if(isSubtree(root->right,subRoot);)
return true;
return false;
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr && q == nullptr)
return true;
if(!(p!=nullptr && q!=nullptr && p->val == q->val))
return false;
bool retl = isSameTree(p->left,q->left);
if(retl == false)
return false;
bool retr = isSameTree(p->right,q->right);
if(retr == false)
return false;
return true;
}
};判斷一個樹是不是另一個的子樹，這里的解法仍然是前序遍歷，思路就是遍歷每一個非空結點，把這個結點看成某一個樹的根節(jié)點，只是這些根節(jié)點或大或小而已，然后調用isSameTree函數(shù)判斷兩個樹是否相同。思路還是那么一個思路，沒什么兩樣。
給出個錯誤解法吧：
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root == nullptr)
return false;
bool ret = isSameTree(root, subRoot);
if(ret == true)
return true;
ret = isSameTree(root->left,subRoot);
if(ret == true)
return true;
ret = isSameTree(root->right,subRoot);
if(ret == true)
return true;
return false;
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr && q == nullptr)
return true;
if(!(p!=nullptr && q!=nullptr && p->val == q->val))
return false;
bool retl = isSameTree(p->left,q->left);
if(retl == false)
return false;
bool retr = isSameTree(p->right,q->right);
if(retr == false)
return false;
return true;
}
};
這是起初寫的錯誤解法，仔細想想還是容易理解的，34，不同，IsSameTree函數(shù)第二個if直接返回false，不會遞歸，然后進入3函數(shù)的左子樹調用，仍然直接返回false，再走到3的右子樹，也是直接返回false。并沒有起到遞歸的作用。
小總結：
簡單來說就是遍歷了一遍， 你可以直接把這個對結點的操作忽略掉，然后只看左遞歸和右遞歸，你就會發(fā)現(xiàn)，這兩個函數(shù)恰好遍歷了一遍整個樹，然后你可以在適當?shù)奈恢脤懸恍┎僮鳎褪菍γ總€結點的操作，比如572這個題，就是比較兩個樹是否相等。
#include<iostream>
#include<assert.h>
#include<string>
using namespace std;
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = new BTNode();
assert(newnode);
newnode->data = x;
newnode->right = nullptr;
newnode->left = nullptr;
return newnode;
}
BTNode* CreateTree(string s, int* pi)
{
if(s[*pi] == '#')
{
(*pi)++;
return NULL;
}
BTNode* root = BuyNode(s[(*pi)++]);
root->left = CreateTree(s, pi);
root->right = CreateTree(s, pi);
return root;
}
void InOrder(BTNode* root)
{
if(root == NULL)
return;
InOrder(root->left);
cout<<root->data<<" ";
InOrder(root->right);
}
int main()
{
string s;
cin >> s;
int i = 0;
BTNode* root = CreateTree(s, &i);
InOrder(root);
return 0;
}這個題相對而言就有點新穎了，創(chuàng)建正確的樹是關鍵。后面的中序遍歷就是一些基本操作了。
有關根據(jù)給定字符串創(chuàng)建合適的二叉樹：其實根本上還是一種前序遍歷的思路，可以直接把這個字符串看作一個正確的二叉樹，s和pi的結合可以逐個遍歷每個字符，每次進入函數(shù)都會創(chuàng)建對應的結點。而遇到#則返回空結點，作為上一個結點的左子樹或者右子樹，并同時結束遞歸。。。。。
- 銷毀二叉樹
void DestroyTree(BTNode* root)
{
if (root == NULL)
{
return;
}
// 后序銷毀，先銷毀左子樹，再銷毀右子樹，最后銷毀根節(jié)點，對于每一棵樹都是這樣的操作。
DestroyTree(root->left);
DestroyTree(root->right);
delete root;
}后序銷毀。。
- 層序遍歷
// 層序遍歷 利用隊列
void LevelOrder(BTNode* root)
{
queue<BTNode*> q;
if (root != NULL)
{
q.push(root);
}
while (!q.empty())
{
BTNode* root = q.front();
cout << root->data << " ";
q.pop();
if (root->left)
{
q.push(root->left);
}
if (root->right)
{
q.push(root->right);
}
}
cout << endl;
}利用隊列，先將根節(jié)點插入隊列，然后出根節(jié)點，進根節(jié)點的兩個子節(jié)點，當然也有可能是一個個，也有可能只有一個根節(jié)點。 每次都是出一個結點，進這個結點的子節(jié)點。達到層序遍歷的目的。
- 利用層序遍歷判斷一顆二叉樹是否是完全二叉樹
bool BinaryTreeComplete(BTNode* root)
{
queue<BTNode*> q;
if (root != NULL)
{
q.push(root);
}
while (!q.empty())
{
BTNode* root = q.front();
q.pop();
if (root)
{
q.push(root->left);
q.push(root->right);
}
else
{
break;
}
}
while (!q.empty())
{
if (q.front() != NULL)
return false;
q.pop();
}
return true;
}完全二叉樹的特點：層序遍歷后，前方遍歷的一定全是非空結點，后方一定全是空結點，利用這一特點進行判斷。即：遇到空結點之后再判斷隊列中是否后續(xù)都是空結點。
到此這篇關于C語言進階二叉樹的基礎與銷毀及層序遍歷詳解的文章就介紹到這了,更多相關C語言二叉樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
shared_ptr?是一個標準的共享所有權的智能指針，允許多個指針指向同一個對象，定義在?memory?文件中，命名空間為?std，這篇文章主要介紹了C++?中?shared_ptr?weak_ptr,需要的朋友可以參考下2022-07-07
序列化是將程序中的對象以一種二進制格式存儲到存儲設備中（例如文本/數(shù)據(jù)庫等），以實現(xiàn)“永生”或隨意“流動”。本文將為大家詳細講講如何基于MFC實現(xiàn)類的序列化，需要的可以參考一下2022-07-07
今天小編就為大家分享一篇C++ 讀取文件內容到指定類型的變量方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
C語言之結構體定義 typedef struct 用法詳解和用法小結
這篇文章主要介紹了C語言的結構體定義typedef struct用法詳解和用法小結，typedef是類型定義，typedef struct 是為了使用這個結構體方便，感興趣的同學可以參考閱讀2023-03-03
這篇文章主要為大家詳細介紹了C++實現(xiàn)公司人事管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
今天小編就為大家分享一篇關于C++構造函數(shù)和析構函數(shù)的使用與講解，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
下面小編就為大家分享一篇c++用指針交換數(shù)組的實例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-11-11
Qt中PaintEvent繪制實時波形圖的實現(xiàn)示例
本文主要介紹了Qt中PaintEvent繪制實時波形圖的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-06-06
本文主要介紹了C++?手擼簡易服務器，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
Dijkstra算法最短路徑的C++實現(xiàn)與輸出路徑
今天小編就為大家分享一篇關于Dijkstra算法最短路徑的C++實現(xiàn)與輸出路徑，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02