二叉樹相關(guān)的算法題

單值二叉樹

如果二叉樹每個(gè)節(jié)點(diǎn)都具有相同的值，那么該二叉樹就是單值二叉樹。

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

示例 1：

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

示例 2：

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

提示：

1. 給定樹的節(jié)點(diǎn)數(shù)范圍是 [1, 100]。
2. 每個(gè)節(jié)點(diǎn)的值都是整數(shù)，范圍為 [0, 99] 。

思路如下：

代碼如下：

/*** 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) {//根節(jié)點(diǎn)為空if(root==NULL){return true;}//根節(jié)點(diǎn)不為空if(root->left&&root->left->val!=root->val){return false;}if(root->right&&root->right->val!=root->val){return false;}return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

相同的樹

給你兩棵二叉樹的根節(jié)點(diǎn) p 和 q ，編寫一個(gè)函數(shù)來檢驗(yàn)這兩棵樹是否相同。

如果兩個(gè)樹在結(jié)構(gòu)上相同，并且節(jié)點(diǎn)具有相同的值，則認(rèn)為它們是相同的。

示例 1：

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

示例 2：

輸入：p = [1,2], q = [1,null,2]
輸出：false

示例 3：

代碼如下：

/*** 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;}//其中一個(gè)為空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);
}

對稱二叉樹

給你一個(gè)二叉樹的根節(jié)點(diǎn) root ， 檢查它是否軸對稱。

示例 1：

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

示例 2：

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

提示：

• 樹中節(jié)點(diǎn)數(shù)目在范圍 [1, 1000] 內(nèi)
• -100 <= Node.val <= 100

這道題是基于上一題相同的樹來完成的。

代碼如下：

/*** 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);//不同點(diǎn)在于這里兩個(gè)樹的結(jié)構(gòu)進(jìn)行比較，不是說樹的內(nèi)部進(jìn)行比較}
bool isSymmetric(struct TreeNode* root) {return isSameTree(root->left,root->right);
}

另一個(gè)樹的子樹

給你兩棵二叉樹 root 和 subRoot 。檢驗(yàn) root 中是否包含和 subRoot 具有相同結(jié)構(gòu)和節(jié)點(diǎn)值的子樹。如果存在，返回 true ；否則，返回 false 。

二叉樹 tree 的一棵子樹包括 tree 的某個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有后代節(jié)點(diǎn)。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 樹上的節(jié)點(diǎn)數(shù)量范圍是 [1, 2000]
• subRoot 樹上的節(jié)點(diǎn)數(shù)量范圍是 [1, 1000]
• -104 <= root.val <= 104
• -104 <= subRoot.val <= 104

代碼如下：

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

這幾道題我們可以發(fā)現(xiàn)重要的規(guī)律，都要用到相同的二叉樹里面的代碼，這里有所不同的地方在于讓根節(jié)點(diǎn)的左右子樹分別和subRoot進(jìn)行比較。

二叉樹的前序遍歷

給你二叉樹的根節(jié)點(diǎn) root ，返回它節(jié)點(diǎn)值的 前序 遍歷。

示例 1：

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

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

示例 4：

輸入：root = [1,2]
輸出：[1,2]

示例 5：

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

提示：

• 樹中節(jié)點(diǎn)數(shù)目在范圍 [0, 100] 內(nèi)
• -100 <= Node.val <= 100

代碼如下：

/*** 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;}return 1+TreeSize(root->left)+TreeSize(root->right);}
//前序遍歷：根左右void _preorderTraversal(TreeNode*root,int*arr,int*pi){if(root==NULL){return;}//為什么這里不是傳值，而是要傳地址呢，因?yàn)閭髦凳欠诺搅硪粔K空間，并沒有改變本身，也就意味著，從始至終都是從0開始//形參要想改變實(shí)參就要傳址調(diào)用arr[(*pi)++]=root->val;_preorderTraversal(root->left,arr,pi);_preorderTraversal(root->right,arr,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {//求節(jié)點(diǎn)個(gè)數(shù)*returnSize=TreeSize(root);//計(jì)算數(shù)組大小int*returnArr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;_preorderTraversal(root,returnArr,&i);return returnArr;
}

二叉樹的中序遍歷

給定一個(gè)二叉樹的根節(jié)點(diǎn) root ，返回 它的 中序 遍歷 。

示例 1：

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

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

• 樹中節(jié)點(diǎn)數(shù)目在范圍 [0, 100] 內(nèi)
• -100 <= Node.val <= 100

代碼如下：

/*** 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;}return 1+TreeSize(root->left)+TreeSize(root->right);}void _inorderTraversal(struct TreeNode*root,int*arr,int*pi){if(root==NULL){return;}_inorderTraversal(root->left,arr,pi);arr[(*pi)++]=root->val;_inorderTraversal(root->right,arr,pi);}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int* returnArr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;_inorderTraversal(root,returnArr,&i);return returnArr;
}

二叉樹的后序遍歷

給你一棵二叉樹的根節(jié)點(diǎn) root ，返回其節(jié)點(diǎn)值的 后序遍歷 。

示例 1：

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

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

• 樹中節(jié)點(diǎn)的數(shù)目在范圍 [0, 100] 內(nèi)
• -100 <= Node.val <= 100

/*** 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;}return 1+TreeSize(root->left)+TreeSize(root->right);}
void _postorderTraversal(struct TreeNode*root,int*arr,int*pi)
{if(root==NULL){return;}_postorderTraversal(root->left,arr,pi);_postorderTraversal(root->right,arr,pi);arr[(*pi)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*returnArr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;_postorderTraversal(root,returnArr,&i);return returnArr;
}

這三道題我們可以感受到只要掌握了怎樣遍歷二叉樹就會(huì)變得簡單許多

二叉樹遍歷

描述

編一個(gè)程序，讀入用戶輸入的一串先序遍歷字符串，根據(jù)此字符串建立一個(gè)二叉樹（以指針方式存儲(chǔ)）。 例如如下的先序遍歷字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空樹。建立起此二叉樹以后，再對二叉樹進(jìn)行中序遍歷，輸出遍歷結(jié)果。

輸入描述：

輸入包括1行字符串，長度不超過100。

輸出描述：

可能有多組測試數(shù)據(jù)，對于每組數(shù)據(jù)， 輸出將輸入字符串建立二叉樹后中序遍歷的序列，每個(gè)字符后面都有一個(gè)空格。 每個(gè)輸出結(jié)果占一行。

示例1

abc##de#g##f###
c b e g d f a 

思路如下：

代碼如下：

include <stdio.h>
#include <stdlib.h>
typedef struct BinaryTreeNode
{char data;struct BinaryTreeNode*left;struct BinaryTreeNode*right;
}BTNode;
BTNode* BuyNode(char x)
{BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));newnode->data=x;newnode->left=newnode->right=NULL;return newnode;
}
BTNode*CreateNode(char*arr,int*pi)
{if(arr[*pi]=='#'){(*pi)++;return NULL;}BTNode*root=BuyNode(arr[(*pi)++]);root->left=CreateNode(arr, pi);root->right=CreateNode(arr, pi);return root;
}void Inorder(BTNode*root)
{if(root==NULL){return;}Inorder(root->left);printf("%c ",root->data);Inorder(root->right);
}
int main() {char arr[100];scanf(" %s ",arr);int i=0;BTNode*root=CreateNode(arr,&i);Inorder(root);return 0;
}