目錄

1 單值二叉樹

2 相同的樹

3 另一顆樹的子樹

4 二叉樹的前序遍歷

5 二叉樹的最大深度

6 對稱二叉樹

7 二叉樹遍歷

---

1 單值二叉樹

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

?

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

2 相同的樹

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

?

/*
* 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 (p->val != q->val){return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}

3 另一顆樹的子樹

572. 另一棵樹的子樹 - 力扣（LeetCode）

?

/*** 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 (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;}if (root->val == subRoot->val){if (isSametree(root, subRoot)){return true;}}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}

4 二叉樹的前序遍歷

144. 二叉樹的前序遍歷 - 力扣（LeetCode）

/*** 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().*/int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void PrevOrder(struct TreeNode* root, int* a, int* i)//這里的i 之所以傳指針是因為遞歸的時候要保存上一次i的值 
{if (root == NULL){return;}a[*i] = root->val;(*i)++;PrevOrder(root->left, a, i);PrevOrder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n = TreeSize(root);int* a = (int*)malloc(sizeof(int) * n);int j = 0;PrevOrder(root, a, &j);//這里j取地址*returnSize = n;return a;
}

5 二叉樹的最大深度

力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int maxDepth(struct TreeNode* root) {if (root == NULL){return 0;}int ret1 = maxDepth(root->left);int ret2 = maxDepth(root->right);return (fmax(ret1, ret2) + 1);}

6 對稱二叉樹

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

/*** 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 (p->val != q->val){return false;}return isSameTree(p->left, q->right) && isSameTree(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {if (root == NULL){return NULL;}return isSameTree(root->left, root->right);
}

7 二叉樹遍歷

二叉樹遍歷_牛客題霸_?？途W

?

#include <stdio.h>
#include<stdlib.h>
typedef struct BianryTreeNode
{struct BianryTreeNode* left;struct BianryTreeNode* right;char val;
}BTNode;BTNode* CreatTree(char* a, int* i)//前序遍歷
{if (a[*i] == '#'){(*i)++;return  NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = a[*i];(*i)++;root->left = CreatTree(a, i);root->right = CreatTree(a, i);return root;
}void PrintInOrder(BTNode* root)//中序遍歷
{if (root == NULL){return;}PrintInOrder(root->left);printf("%c ", root->val);PrintInOrder(root->right);
}
int main() {char arr[100];scanf("%s", arr);int i = 0;BTNode* root = CreatTree(arr, &i);PrintInOrder(root);return 0;
}

本節(jié)對二叉樹的一些常規(guī)OJ題目進行了代碼實現和講解, 雖然圖解很少, 但是大家根據代碼和注釋也可以很好理解,也可以自己畫一畫遞歸展開圖.本節(jié)對二叉樹鏈式結構的基礎要求很高, 大家如果基礎不好,可以先看看我之前的博客.

繼續(xù)加油!