C語言進階二元樹的基礎與銷燬及層序遍歷詳解

2022-06-24 14:05:54

單值二元樹

難度簡單

如果二元樹每個節點都具有相同的值，那麼該二元樹就是單值二元樹。

只有給定的樹是單值二元樹時，才返回true；否則返回false。

範例 1：

輸入：[1,1,1,1,1,null,1]
輸出：true

範例 2：

輸入：[2,2,2,5,2]
輸出：false

提示：

給定樹的節點數範圍是[1, 100]。

每個節點的值都是整數，範圍為[0, 99]。

解1：

最簡單易懂的解法，先序遍歷一遍，把每個節點都和那個根節點的val值相比。最後判斷flag是否為真，若為假，則表明樹中有某節點的值不符。

其中的return語句是為了避免一些無意義的比較，但是其實第一個if的flag判斷完全可以寫在左遞迴之後，判斷一下，如果左遞迴將flag置為了假，則直接return，不會進入右子樹。如果按照上方解法來說，就是進入右子樹之後，發現flag為假，再退出。

OJ題裡的全域性變數需要小心使用，若isUnivalTree裡的flag不置為真，則多個測試用例時，可能會承接上一個測試用例假的結果。發生錯誤。

解法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);
    }
};

判斷每個結點和其兩個子節點是否相同，當然，需要確保子節點非空，若存在不同的，直接返回false，然後遞迴其左右子樹。

其實這個的實質就是前序遍歷，對每個結點的操作就是比較它和兩個子節點的值是否相同。每個結點如果都和其左右子結點相同，那麼這棵樹也就都相同了，如果某處不同，則返回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

給你兩棵二元樹的根節點p和q，編寫一個函數來檢驗這兩棵樹是否相同。

如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。

範例 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

提示：

兩棵樹上的節點數目都在範圍[0, 100]內
-104<= Node.val <= 104

通過次數344,943提交次數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

給你一個二元樹的根節點root，檢查它是否軸對稱。

範例 1：

輸入：root = [1,2,2,3,4,4,3]
輸出：true

範例 2：

輸入：root = [1,2,2,null,3,null,3]
輸出：false

提示：

樹中節點數目在範圍[1, 1000]內
-100 <= Node.val <= 100

進階：你可以運用遞迴和迭代兩種方法解決這個問題嗎？

通過次數603,527提交次數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;
        // 兩者根節點不相等，結束，不需要進一步判斷了。
        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具有相同結構和節點值的子樹。如果存在，返回true；否則，返回false。

二元樹tree的一棵子樹包括tree的某個節點和這個節點的所有後代節點。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樹上的節點數量範圍是[1, 2000]
subRoot樹上的節點數量範圍是[1, 1000]
-104<= root.val <= 104
-104<= subRoot.val <= 104

通過次數125,811提交次數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;
    }
};

判斷一個樹是不是另一個的子樹，這裡的解法仍然是前序遍歷，思路就是遍歷每一個非空結點，把這個結點看成某一個樹的根節點，只是這些根節點或大或小而已，然後呼叫isSameTree函數判斷兩個樹是否相同。思路還是那麼一個思路，沒什麼兩樣。

給出個錯誤解法吧：

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函數第二個if直接返回false，不會遞迴，然後進入3函數的左子樹呼叫，仍然直接返回false，再走到3的右子樹，也是直接返回false。並沒有起到遞迴的作用。

小總結：

簡單來說就是遍歷了一遍，你可以直接把這個對結點的操作忽略掉，然後只看左遞迴和右遞迴，你就會發現，這兩個函數恰好遍歷了一遍整個樹，然後你可以在適當的位置寫一些操作，就是對每個結點的操作，比如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;
}

這個題相對而言就有點新穎了，建立正確的樹是關鍵。後面的中序遍歷就是一些基本操作了。

有關根據給定字串建立合適的二元樹：其實根本上還是一種前序遍歷的思路，可以直接把這個字串看作一個正確的二元樹，s和pi的結合可以逐個遍歷每個字元，每次進入函數都會建立對應的結點。而遇到#則返回空結點，作為上一個結點的左子樹或者右子樹，並同時結束遞迴。。。。。

銷燬二元樹

void DestroyTree(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	// 後序銷燬，先銷燬左子樹，再銷燬右子樹，最後銷燬根節點，對於每一棵樹都是這樣的操作。
	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;
}

利用佇列，先將根節點插入佇列，然後出根節點，進根節點的兩個子節點，當然也有可能是一個個，也有可能只有一個根節點。每次都是出一個結點，進這個結點的子節點。達到層序遍歷的目的。

利用層序遍歷判斷一顆二元樹是否是完全二元樹

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;
}

完全二元樹的特點：層序遍歷後，前方遍歷的一定全是非空結點，後方一定全是空結點，利用這一特點進行判斷。即：遇到空結點之後再判斷佇列中是否後續都是空結點。

到此這篇關於C語言進階二元樹的基礎與銷燬及層序遍歷詳解的文章就介紹到這了,更多相關C語言二元樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

C語言進階二元樹的基礎與銷燬及層序遍歷詳解

熱門文章