上回我們手撕了一棵二叉樹,并且通過遞歸完成了遍歷,這回我們將深入理解用遞歸解決相關(guān)的二叉樹問題,數(shù)量使用分治的思想.

上回的代碼:

#include<stdio.h>
#include<stdlib.h>
typedef struct BinTreeNode
{struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;
BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}
BTNode* CreateTree()
{BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}
void PreOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}int main()
{BTNode* root = CreateTree();printf("前序遍歷:");PreOrder(root);printf("\n");printf("中序遍歷:");InOrder(root);printf("\n");printf("后序遍歷:");PostOrder(root);printf("\n");return 0;
}

一、求二叉樹存儲的元素個數(shù)

這里我的思路很簡單，我們可以通過遞歸將二叉樹向左右孩子遍歷，不為空則加1.

代碼如下：

int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

二、二叉樹的最大深度

這個思路整體也不難，我們一樣用遞歸左右孩子節(jié)點，每通過一個非0的節(jié)點加1，NULL則直接返回，然后左右節(jié)點的返回值比較，最后返回大的值。

代碼如下：

int maxDepth(BTNode* root)
{if (root == NULL)return 0;int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

三、尋找X的所在的節(jié)點

這個就是在左右遞歸上加上判斷val是否等于X

代碼示例：

BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* ret1 = TreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = TreeFind(root->right, x);if (ret2)return ret2;return NULL;
}

四、單值二叉樹

965. 單值二叉樹 - 力扣（LeetCode）

bool isUnivalTree(struct TreeNode* root) {if(root==NULL)return true;if (root->left) {if (root->val != root->left->val || !isUnivalTree(root->left)) {return false;}}if (root->right) {if (root->val != root->right->val || !isUnivalTree(root->right)) {return false;}}return true;
}

運用遞歸判斷只要存在一個false最后結(jié)果必然false

五、相同的樹

100. 相同的樹 - 力扣（LeetCode）

bool isSameTree(struct TreeNode* p, struct 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);
}

這題思路和上題差不多,排除特殊情況就行。

六、對稱二叉樹

101. 對稱二叉樹 - 力扣（LeetCode）

bool judge(struct TreeNode *p ,struct TreeNode *q){if(p == NULL && q == NULL){return true;}else if(p == NULL || q == NULL){return false;}else if(p -> val != q -> val){return false;}return judge(p -> left,q -> right) && judge(p -> right,q -> left);
}
bool isSymmetric(struct TreeNode* root){return judge(root -> left,root -> right);
}

這題思路和上題也大差不差,我把遞歸內(nèi)容拉出來了而已

---

希望這篇學(xué)習(xí)之后，大家能學(xué)會這種分治的思想，謝謝閱讀。