C語言進階二叉樹的基礎(chǔ)與銷毀及層序遍歷詳解

更新時間：2022年06月24日 10:20:25 作者：配的上了嗎

朋友們好,這篇播客我們繼續(xù)C++的初階學(xué)習(xí)，現(xiàn)在對我們對C++的二叉樹基礎(chǔ)oj與二叉樹銷毀和層序遍歷進行練習(xí)，讓我們相互學(xué)習(xí),共同進步

單值二叉樹

難度簡單

如果二叉樹每個節(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不置為真，則多個測試用例時，可能會承接上一個測試用例假的結(jié)果。發(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é)點是否相同，當(dāng)然，需要確保子節(jié)點非空，若存在不同的，直接返回false，然后遞歸其左右子樹。

其實這個的實質(zhì)就是前序遍歷，對每個結(jié)點的操作就是比較它和兩個子節(jié)點的值是否相同。每個結(jié)點如果都和其左右子結(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é)構(gòu)上相同，并且節(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]內(nèi)
-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]內(nèi)
-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)  // 都是空，結(jié)束遞歸，且符合條件
            return true;
        // 兩者根節(jié)點不相等，結(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é)構(gòu)和節(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é)點看成某一個樹的根節(jié)點，只是這些根節(jié)點或大或小而已，然后調(diào)用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ù)的左子樹調(diào)用，仍然直接返回false，再走到3的右子樹，也是直接返回false。并沒有起到遞歸的作用。

小總結(jié)：

簡單來說就是遍歷了一遍，你可以直接把這個對結(jié)點的操作忽略掉，然后只看左遞歸和右遞歸，你就會發(fā)現(xiàn)，這兩個函數(shù)恰好遍歷了一遍整個樹，然后你可以在適當(dāng)?shù)奈恢脤懸恍┎僮?，就是對每個結(jié)點的操作，比如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)建正確的樹是關(guān)鍵。后面的中序遍歷就是一些基本操作了。

有關(guān)根據(jù)給定字符串創(chuàng)建合適的二叉樹：其實根本上還是一種前序遍歷的思路，可以直接把這個字符串看作一個正確的二叉樹，s和pi的結(jié)合可以逐個遍歷每個字符，每次進入函數(shù)都會創(chuàng)建對應(yīng)的結(jié)點。而遇到#則返回空結(jié)點，作為上一個結(jié)點的左子樹或者右子樹，并同時結(jié)束遞歸。。。。。

銷毀二叉樹

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é)點，當(dāng)然也有可能是一個個，也有可能只有一個根節(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;
}

完全二叉樹的特點：層序遍歷后，前方遍歷的一定全是非空結(jié)點，后方一定全是空結(jié)點，利用這一特點進行判斷。即：遇到空結(jié)點之后再判斷隊列中是否后續(xù)都是空結(jié)點。

到此這篇關(guān)于C語言進階二叉樹的基礎(chǔ)與銷毀及層序遍歷詳解的文章就介紹到這了,更多相關(guān)C語言二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: