【數據結構入門】二叉樹（2）

1.二叉樹遍歷順序

1.1 前序（先根）遍歷

1.2 中序（中根）遍歷

1.3 后序（后根）遍歷

1.4 層序遍歷

1.5 深度優先遍歷&廣度優先遍歷

2.二叉樹的遍歷

2.1 前根遍歷（遞歸）

?2.1.1 多路遞歸分析

2.1.2 OJ題目：前序遍歷

2.1.3 OJ題目：單值二叉樹

2.2 中根后根遍歷（遞歸）

3. 二叉樹的節點數量

4.?求二叉樹葉子結點數量

5. 求二叉樹深度

6.OJ:翻轉二叉樹

7.相同的樹

8.另一個樹的子樹

1.二叉樹遍歷順序

? ? ? ? 對于任意一個鏈式二叉樹而言，可以將其看成三部分：根結點、左子樹、右子樹。

1.1 前序（先根）遍歷

先遍歷根節點，再遍歷左節點，再遍歷右節點。對于上圖而言的遍歷順序為，A->B->D->E->C；

1.2 中序（中根）遍歷

先遍歷左節點，再遍歷根結點，最后遍歷右節點。對于上圖而言的遍歷順序為，D->B->E->A->C;

1.3 后序（后根）遍歷

先遍歷左節點，再遍歷右節點，最后遍歷根結點。對于上圖而言的遍歷順序為，D->E->B->C->A

1.4 層序遍歷

顧名思義按照一層一層來遍歷所有的節點，A->B->C->D->E? ?，層序遍歷可以用來判斷是否是完全二叉樹，因為如果將NULL節點打印出來的話，其實可以發現A->B->C->D->E NULL?NULL?NULL?NULL?NULL?NULL

有效節點和空節點其實是分開的，這就可以判斷是否是完全二叉樹。

1.5 深度優先遍歷&廣度優先遍歷

深度優先可以理解先朝著深處遍歷，實在不能遍歷，再進行回溯，例如前中后序遍歷；

廣度優先可以理解為以跟為中心點，一層一層往外擴張，層序遍歷就是廣度優先遍歷。

2.二叉樹的遍歷

2.1 前根遍歷（遞歸）

????????想要遍歷以上的二叉樹，我們可以使用上面介紹的遍歷方法，由于樹的結構就是天然的遞歸結構，那么我們可以使用遞歸方法來遍歷樹。

? ? ? ? 首先需要創建一個二叉樹的結構體，該結構體需要左子樹指針右子樹指針以及當前節點存放的數據。

? ? ? ? 對于先根遍歷，對于每一個節點來說都是先打印根結點再打印左子樹再打印右子樹，所以函數進入之后，直接打印根結點，遞歸調用自己的左子樹和右子樹，如果當前節點為空，那么說明已經到了葉子結點，需要進行函數的回退。

typedef struct BinaryTreeNode
{dataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BinaryTreeNode;// 遍歷
void PreOrder(BinaryTreeNode* root)
{if (root == NULL){return;}// 先根printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}// 創建二叉樹節點
BinaryTreeNode* CreateNode(char x) 
{BinaryTreeNode* ret = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));ret->data = x;ret->left = NULL;ret->right = NULL;return ret;
}// 求二叉樹的大小int main() 
{BinaryTreeNode* A = CreateNode('A');BinaryTreeNode* B = CreateNode('B');BinaryTreeNode* C = CreateNode('C');BinaryTreeNode* D = CreateNode('D');BinaryTreeNode* E = CreateNode('E');A->left = B;A->right = C;B->left = D;B->right = E;PreOrder(A);
}

?2.1.1 多路遞歸分析

? ? ? ? 我們簡單地對上面這個先根遍歷進行展開，首先節點A進入函數，打印A節點，調用A的左子樹，將B作為新函數的root節點，打印B，將B的左子樹作為新函數的根結點，打印D，將D的左子樹作為根節點，判斷為空那么函數就返回上一層調用函數的位置，繼續執行將B的右子樹傳入函數，打印B的右子樹E，將B的左子樹作為函數的參數調用，打印D，將D的左子樹作為參數調用函數，由于D的左孩子是NULL，此時函數直接返回到上一層，將D的右孩子作為參數進行調用，此時D的右孩子是NULL，繼續返回上一層，發現上一層函數執行完畢，那么就繼續調用根為B的節點的右孩子的遞歸，此時B的右孩子是E，打印E，將E的左右孩子作為參數進行遞歸調用，由于均是NULL，所以直接返回，最后B作為根節點的函數已經調用完畢，最后再調用以A為節點的函數，此時函數執行到了A節點的右孩子，最終打印C，以及C的左右孩子均為NULL，所以直接返回。

2.1.2 OJ題目：前序遍歷

二叉樹的前序遍歷

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

示例 1：

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

輸出：[1,2,3]

解釋：

????????這道題目本身的邏輯不難，需要思考的是，如何將本該輸出的操作轉換為存入數組，首先需要傳入一個數組，一個下標的指針，這里傳入指針是因為，下標始終貫穿整個遞歸結構，不能被銷毀，需要一直存在；

? ? ? ? 當將i下標的位置的元素賦值以后，需要立刻將下標++，再進行遞歸調用左子樹和右子樹。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct TreeNode TreeNode;int treeSize(TreeNode* root){if(root == NULL){return 0;}else{return 1 + treeSize(root->left) + treeSize(root->right);}}void preOrder(TreeNode* root,int* arr, int* i)
{if(root == NULL){return;}// 放入數組arr[(*i)] = root->val; ++(*i);preOrder(root->left,arr,i);preOrder(root->right,arr,i);}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int* ret = (int*) malloc(sizeof(int)*treeSize(root));int i = 0;preOrder(root,ret,&i);*returnSize = treeSize(root);return ret;
}

2.1.3 OJ題目：單值二叉樹

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

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

示例 1：

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

? ? ? ? 先考慮當前樹，在考慮左右子樹。

? ? ? ? 首先判斷單個節點為空，那么說明為真，因為空節點其實不影響判斷單值。

? ? ? ? 若根結點不為空，在左節點不為空的情況下，如果左節點的值和根結點的值不等，說明不是單值，返回false；

? ? ? ? 右節點同理；

? ? ? ? 最后判斷左子樹和右子樹如果同時是true，說明左右子樹都是單值，若有一個為false說明就不是單值。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) {// 只有一個節點是單值二叉樹if(root == NULL){return true;}// 當左節點和根結點不相等返回假if(root->left != NULL && root->val != root->left->val){return false;}// 當右節點和根結點不相等返回假if(root->right!= NULL && root->val != root->right->val){return false;}// 左子樹和右子樹return isUnivalTree(root->left) && isUnivalTree(root->right);}

2.2 中根后根遍歷（遞歸）

? ? ? ? 如果理解了前序遍歷，那么中根遍歷其實就是先訪問左子樹再打印根，訪問右子樹。

// 中序遍歷
void InOrder(BinaryTreeNode* root)
{if (root == NULL){return;}PreOrder(root->left);printf("%c ", root->data);PreOrder(root->right);
}// 后序遍歷
void PostOrder(BinaryTreeNode* root)
{if (root == NULL){return;}PreOrder(root->left);PreOrder(root->right);printf("%c ", root->data);
}

3. 二叉樹的節點數量

? ? ? ? 同樣可以使用遞歸來求，如果當前節點是NULL，那么就直接結束該函數，不然就將size++，這里需要注意的是由于遞歸調用函數是棧，在函數內定義size，每次函數結束的時候size會銷毀，所以這里需要把size設置成靜態局部變量。

? ? ? ? ++完size之后需要遍歷左子樹和右子樹，這里遍歷的順序沒有要求。

// 求二叉樹的大小
int TreeSize(BinaryTreeNode* root)
{static int size = 0;if (root == NULL){return 0;}++size;// 遍歷左右子樹TreeSize(root->left);TreeSize(root->right);return size;
}

? ? ? ? 這里有一個致命的問題，如果這個函數被調用多次，那么次數是會被累加計算的，因為函數執行結束的時候該變量是存儲在靜態區中，是不會被銷毀的。

? ? ? ? 所以這里的size是由外界傳入的，如果此節點非空那么size++，這樣也會解決上述提到的問題。

// 求二叉樹的大小
void  TreeSize(BinaryTreeNode* root, int* size)
{if (root == NULL){return;}++(*size);// 遍歷左右子樹TreeSize(root->left, size);TreeSize(root->right, size);
}int main()
{BinaryTreeNode* A = CreateNode('A');BinaryTreeNode* B = CreateNode('B');BinaryTreeNode* C = CreateNode('C');BinaryTreeNode* D = CreateNode('D');BinaryTreeNode* E = CreateNode('E');A->left = B;A->right = C;B->left = D;B->right = E;//PreOrder(A);int size = 0;TreeSize(A, &size);printf("%d ", size);
}

????????但是這種方法需要傳入一個size，對于調用方法的人來說非常不友好，那么有沒有一種方法，可以直接返回當前的根結點的二叉樹節點數呢？

? ? ? ? 若節點為空，返回0，若不為空就返回1（本身）+左子樹+右子樹的節點數量。

// 求二叉樹的大小
int  TreeSize(BinaryTreeNode* root)
{if (root == NULL){return 0;}else{return 1 + TreeSize(root->left) + TreeSize(root->right);}
}

4.?求二叉樹葉子結點數量

? ? ? ? 首先使用遞歸來解決，判斷當前節點是否為空節點，然后判斷當前節點是否為葉子結點（左右子樹為空），最后就是普通的節點，此時計算該葉子結點是左子樹葉子結點+右子樹葉子結點。


// 求二叉樹葉子結點個數
int LeafSize(BinaryTreeNode* root) 
{// 是空嗎if (root == NULL) {return 0;}// 是葉子節點嗎if (root->right == NULL && root->left == NULL) {return 1;}return LeafSize(root->left) + LeafSize(root->right);
}

5. 求二叉樹深度

? ? ? ? 如果空節點，深度為0；除此以外，剩下的節點都按照左子樹深度和右子樹深度中最大的那一個再+1（本節點）計算。

// 二叉樹的深度
int TreeDepth(BinaryTreeNode* root) 
{// 如果空節點深度就是0if (root == NULL) {return 0;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

6.OJ:翻轉二叉樹

給定一棵二叉樹的根節點?root，請左右翻轉這棵二叉樹，并返回其根節點。

示例 1：

輸入：root = [5,7,9,8,3,2,4]
輸出：[5,9,7,4,2,3,8]

????????如果根結點為空，直接返回NULL，如果不為空就交換根結點的左右節點，應用在左子樹和右子樹上，最后返回根結點。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* flipTree(struct TreeNode* root) {if (root == NULL) {return NULL;}struct TreeNode* tmp = root->left;root->left = root->right;root->right = tmp;flipTree(root->left);flipTree(root->right);return root;
}

????????還有一種解法：剛剛的解法是先處理根結點在處理左子樹和右子樹，屬于前序遍歷，那么可以先處理左右子樹，在處理根結點。????????

例如先將，2和7的子樹進行翻轉，最后將4的right連到2,4的left連接到7；

struct TreeNode* flipTree(struct TreeNode* root) {if (root == NULL) {return NULL;} else {struct TreeNode* tmp = root->right;root->right = flipTree(root->left);root->left = flipTree(tmp);return root;}
}

7.相同的樹

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

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

示例 1：

輸入：p = [1,2,3], q = [1,2,3]
輸出：true

首先如果兩個節點都是空，那么說明完全是相同的，直接返回true；

若一個節點為空另一個節點不為空，說明兩個節點結構不同，返回false；

若兩個節點都不為空，并且值還不相等，說明這兩個節點不相等，返回false；

最后判斷左右子樹為true的情況下返回true，否則false；

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {// 都是空也相等if (p == NULL && q == NULL) {return true;}// 結構不同if (p == NULL && q != NULL) {return false;}if (q == NULL && p != NULL) {return false;}// qp都不為空，值不同if (p->val != q->val) { //此時如果兩個值相同依舊不能判斷結果，因為沒有判斷左右子樹，所以這里判斷不相等的時候return false;} // 結構相同、值相同，判斷左右子樹return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

8.另一個樹的子樹

給你兩棵二叉樹?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

從示例2可以得出，子樹的定義是某一個子樹到葉子結點與提供的子樹完全相同，子樹不能有子樹。

? ? ? ? 首先需要判斷主樹為空，那么就不需要判斷子樹了，沒有樹是NULL的子樹，返回false；

然后判斷若兩棵樹如果是同一棵樹（借助上一題的接口），那么就返回true；

如果沒有找到，那么就去遞歸左子樹，若左子樹沒找到，再遞歸右子樹。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool isSameTree(struct TreeNode* p, struct TreeNode* q) {// 都是空也相等if (p == NULL && q == NULL) {return true;}// 結構不同if (p == NULL && q != NULL) {return false;}if (q == NULL && p != NULL) {return false;}// qp都不為空，值不同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) {// 如果主樹是空的，就不需要比了if(root == NULL){return false;}// 如果主樹和子樹比對上了，返回trueif(isSameTree(root,subRoot)){return true;}// 如果沒找到，先去左子樹找，左子樹沒找到去右子樹return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}