目錄

1? 另一棵樹的子樹?

?1）?題目描述

示例1：

示例2：

2） 算法解析

3） 代碼

2? 二叉樹的遍歷

1） 問題描述

2） 算法解析

3） 代碼

3? 總結??

---

1? 另一棵樹的子樹?

leetcode鏈接https://leetcode.cn/problems/subtree-of-another-tree/description/

---

?1）?題目描述

? 給你兩棵二叉樹?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 這棵樹中是否有 subRoot 這棵樹，不管是相同的樹，還是左子樹中有與subRoot 相同的樹或者是在右子樹中有與 subRoot 相同的樹，subRoot 都算是 root 的子樹。

---

2） 算法解析

? 該題目可以采用遞歸算法來解決。這道題的解決需要使用到前一篇文章里的相同的樹的算法，因為判斷 subRoot 是否是 root 的子樹，本質上就是判斷 root 里是否有與 subRoot 相同的樹，具體算法思想描述如下：
? 該遞歸算法可以抽象為 root 的左子樹里是否有與 subRoot 相同的樹或者右子樹里是否有與 subRoot 相同的樹，這個就是遞歸解決該問題的過程。邊界條件共有兩條：（1） 如果 root 本身是一棵空樹，那么 root 里肯定沒有與 subRoot 相同的樹，直接返回 false；（2） 如果 root 這棵樹本身就是與 subRoot 相同的樹，說明 subRoot 是 root 的一棵子樹，那就返回 true。

---

3） 代碼

typedef struct TreeNode TreeNode;//判斷相同的樹bool isSameTree(TreeNode* p, TreeNode* q){if (p == NULL && q == NULL){return true;}if (p == NULL || q == NULL){return false;}if (p->val != q->val){return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{//如果root為空，那就返回falseif (root == NULL){return false;}//如果兩個結點對應的樹是相同的樹，返回trueif (isSameTree(root, subRoot)){return true;}//判斷subRoot是否是左子樹或者右子樹的子樹return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

---

2? 二叉樹的遍歷

leetcode鏈接https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

---

1） 問題描述

? 給你二叉樹的根節點?root?，返回它節點值的?前序?遍歷。

? 這里看似是一個簡單的前序遍歷，但是其實沒有那么簡單，我們來看一下函數頭部：

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{}

? 可以看到其返回值為 int* ，也就是一個指針，并不像之前我們寫過的前序遍歷一樣返回值為 void。實際上這里是需要返回一個存儲了節點前序遍歷值的數組，所以返回值才為 int*。

---

2） 算法解析

? 這里最大的難點就在與如何將前序遍歷的結果存儲在數組里面，而且所給的函數頭部里面也有一個 returnSize 參數，通過名字可以看出來，該參數的作用實際上就是返回數組的大小，所以我們不僅需要將數組返回，還得計算數組中有多少元素，也就是二叉樹里面有多少節點。所以我們需要首先計算二叉樹里面節點的個數（在鏈式二叉樹文章中提到過相關操作的實現），所以這里總共需要 3 個函數：

（1） TreeSize函數：用來計算二叉樹里面節點的個數。

（2） PreOrder函數：用來進行前序遍歷，將結果存儲在數組中。

（3） preorderTraversal函數：用來創建數組，返回存儲結果的數組。

? 接下來我們來講解如何將前序遍歷的結果存儲在數組中。

? 可能開始我們想的是按照前序遍歷的代碼，只需將打印的地方改為向數組中存儲值即可：

void PreOrder(TreeNode* root, int* arr)
{int i = 0;if (root == NULL){return;}arr[i] = root->val;i++;PreOrder(root->left, arr);PreOrder(root->right, arr);
}

但是這樣會存在一個問題，就是在不斷遞歸的過程中，每次進入新的遞歸的時候，里面的 i 都會變成0，也就是總是往 arr[0] 位置存儲前序遍歷的結果，這里借助函數棧幀（每次調用函數時，會新開辟的一塊空間，每個函數的空間是獨立的）的概念來解釋：

可以看到每次調用PreOrder函數，都會新開辟一塊空間，所以其實里面的 i 都是屬于不用空間的，一個 i 改變并不會影響另一個函數里面的 i ，所以每次遞歸調用函數 i 都是為 0 的。

? 那么要想在遞歸過程中改變這個下標，我們就需要傳遞一個整形的地址，讓其能夠找到存儲 arr 下標的空間，讓存儲空間里面的值改變，就會讓下標隨著遞歸的而改變了：

//arr為數組收元素的地址，pi為存儲arr數組下標的地址
void PreOrder(TreeNode* root, int* arr, int* pi)
{if (root == nullptr){return;}arr[(*pi)++] = root->val;PreOrder(root->left);PreOrder(root->right);
}

這里就可以通過一個指針變量 pi 來指向存儲 arr 數組下標的空間（傳參時傳遞一個值為 0 的整型的地址即可），?這樣通過 pi 就可以間接改變 arr 數組中的值了。

---

3） 代碼

typedef struct TreeNode TreeNode;//先計算樹的結點個數，依結點個數開辟數組空間int TreeSize(TreeNode* root){if (root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);}
//將前序遍歷的序列存入數組中
void PreOrder(TreeNode* root, int* arr, int* pi)
{if (root == NULL){return;}arr[(*pi)++] = root->val;//遍歷左子樹PreOrder(root->left, arr, pi);//遍歷右子樹PreOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize = TreeSize(root);int* arr = (int*)malloc(sizeof(int) * (*returnSize));if (arr == NULL){perror("malloc fail！\n");exit(1);}int n = 0;PreOrder(root, arr, &n);return arr;
}

---

3? 總結??

? 在該題目中，我們解決了如何在遞歸過程中向數組中存儲數據的問題。只需用一個指針變量間接改變即可。所以以后如果遇到類似問題，一定要想到利用指針來改變下標。

? 當然，除了前序遍歷，還有中序遍歷和后序遍歷，在講解完前序遍歷之后，相信這兩個遍歷也很簡單了，可以自己嘗試一下：
中序遍歷https://leetcode.cn/problems/binary-tree-inorder-traversal/代碼：

typedef struct TreeNode TreeNode;//返回樹的結點個數int TreeSize(TreeNode* root){if (root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);}
//中序遍歷樹，把遍歷數據存放在數組里面
void InOrder(TreeNode* root, int* arr, int* pi)
{if (root == NULL){return;}InOrder(root->left, arr, pi);arr[(*pi)++] = root->val;InOrder(root->right, arr, pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{*returnSize = TreeSize(root);int* arr = (int*)malloc(sizeof(int) * (*returnSize));if (arr == NULL){perror("malloc fail！\n");exit(1);}int n = 0;InOrder(root, arr, &n);return arr;
}

---

后序遍歷https://leetcode.cn/problems/binary-tree-postorder-traversal/description/代碼：

typedef struct TreeNode TreeNode;//求節點個數int TreeSize(TreeNode* root){if (root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);}//二叉樹的后序遍歷并將遍歷結果保存到數組中
void PostOrder(int* arr, TreeNode* root, int* i)
{if (root == NULL){return;}//遍歷左子樹PostOrder(arr, root->left, i);//遍歷右子樹PostOrder(arr, root->right, i);arr[(*i)++] = root->val;}int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);//根據二叉樹節點空間開辟數組int* arr = (int*)malloc(sizeof(int) * (*returnSize));int i = 0;PostOrder(arr, root, &i);return arr;
}