前言：本章將通過五道來自LeetCode/牛客網中的二叉樹相關演算法題來介紹資料結構中二叉樹在演算法題中的應用，題目難度不大，大家就當放松放松，
文章目錄
- 1.二叉樹的最大深度
- 思路分析：
- 題解：
- 2.平衡二叉樹
- 思路分析：
- 題解：
- 3.二叉樹的后序遍歷
- 思路分析：
- 題解：
- 4.二叉樹的中序遍歷
- 思路分析：
- 題解：
- 5.翻轉二叉樹
- 思路分析：
- 題解：
1.二叉樹的最大深度
OJ鏈接
給定一個二叉樹，找出其最大深度，
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，
思路分析：
二叉樹的最大深度等價于：左右子樹的最大深度 + 1
題解：
int maxDepth(struct TreeNode* root){
if(root==NULL)
{
return 0;
}
int left=maxDepth(root->left)+1;
int right=maxDepth(root->right)+1;
if(left>right)
{
return left;
}
return right;
}
2.平衡二叉樹
OJ鏈接
判斷一顆二叉樹是否是平衡二叉樹
思路分析：
首先要保證當前樹的左右子樹高度差不大于1（可用絕對值函式abs（x，y）判斷），并且子樹本身也是平衡樹，
題解：
int MaxDepth(struct TreeNode* root)
{
return root?1+fmax(MaxDepth(root->left),MaxDepth(root->right)):0;
}
bool isBalanced(struct TreeNode* root){
if(root==NULL)
{
return true;
}
int left=MaxDepth(root->left);
int right=MaxDepth(root->right);
return abs(left-right)<2&&isBalanced(root->left)&&isBalanced(root->right);
}
3.二叉樹的后序遍歷
OJ鏈接
給定一個二叉樹，回傳它的 后序 遍歷，
思路分析：
沒啥好說的，參照上一篇前序遍歷，類似
題解：
int TreeSize(struct TreeNode*root) //求出二叉樹中節點個數
{
if(root==NULL)
{
return 0;
}
return TreeSize(root->left)+TreeSize(root->right)+1;
}
int _postorderTraversal(struct TreeNode* root, int* arr,int* i)
{
if(root==NULL)
{
return;
}
_postorderTraversal(root->left,arr,i);
_postorderTraversal(root->right,arr,i);
arr[(*i)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize=TreeSize(root);
int* arr=malloc(sizeof(int)* *returnSize);
int i=0;
_postorderTraversal(root,arr,&i);//這邊i務必傳指標，每個遞回呼叫堆疊幀中都有一個i，傳值的話下一層++i不會對上一層造成影響
return arr;
}
4.二叉樹的中序遍歷
OJ鏈接
給定一個二叉樹的根節點
root，回傳它的 中序 遍歷，
思路分析：
沒啥好說的，和前序后序類似
題解：
int TreeSize(struct TreeNode*root) //求出二叉樹中節點個數
{
if(root==NULL)
{
return 0;
}
return TreeSize(root->left)+TreeSize(root->right)+1;
}
int _inorderTraversal(struct TreeNode* root, int* arr,int* i)
{
if(root==NULL)
{
return;
}
_inorderTraversal(root->left,arr,i);
arr[(*i)++]=root->val;
_inorderTraversal(root->right,arr,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize=TreeSize(root);
int* arr=malloc(sizeof(int)* *returnSize);
int i=0;
_inorderTraversal(root,arr,&i);//這邊i務必傳指標，每個遞回呼叫堆疊幀中都有一個i，傳值的話下一層++i不會對上一層造成影響
return arr;
}
5.翻轉二叉樹
OJ鏈接
翻轉一棵二叉樹，
思路分析：
翻轉每一棵樹的左右子樹根節點
題解：
void _invertTree(struct TreeNode* root){
if(root==NULL)
{
return 0;
}
struct TreeNode*tmp=root->left;
root->left=root->right;
root->right=tmp;
_invertTree(root->left);
_invertTree(root->right);
}
struct TreeNode* invertTree(struct TreeNode* root){
if(root==NULL)
{
return 0;
}
_invertTree(root);
return root;
}
*資料結構的二叉樹入門練習內容（下）到此介紹結束了，感謝您的閱讀！！！如果內容對你有幫助的話，記得給我三連（點贊、收藏、關注）——做個手有余香的人，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/319869.html
標籤：其他