二分木は、以下を含みます：
- ノード要素；
- 子ノードを指すポインタ
Left； - もう一方の子ノードを指すポインタ
Right。
LeetCodeにおける木の表現方法：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};leetcode104. 二分木の最大深さ#
int maxDepth(TreeNode* root) {
if(root==nullptr){
return 0;
}
return max(maxDepth(root->left),maxDepth(root->right))+1;
}- 最初は左右の子木の深さを再帰的に計算します #再帰
max()は最大深さ +1 を返します
leetcode226. 二分木の反転#
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr){
return nullptr;
}
TreeNode* temp;
temp=root->left;
root->left=root->right;
root->right=temp;
invertTree(root->left);
invertTree(root->right);
return root;
}二分木を再帰的にトラバースし、各ノードの左右の子ノードを入れ替えることで、二分木の鏡像（ミラー）を生成することを検討します。
- 時間計算量：O(n)
- 空間計算量：O(n)
leetcode101. 対称な二分木#
bool isSymmetric(TreeNode* root) {
if(root==nullptr){
return true;
}
return isMirror(root->left,root->right);
}
bool isMirror(TreeNode* root1,TreeNode* root2){
if(root1==nullptr&&root2==nullptr){
return true;
}
if(root1==nullptr||root2==nullptr||root1->val!=root2->val){
return false;
}
return(isMirror(root1->left,root2->right)&&isMirror(root1->right,root2->left));
}- 時間計算量：O(n)
- 空間計算量：O(n)
関数 isSymmetric() :
- 特殊ケースの処理：根ノード
rootが空の場合は、直接trueを返します。 - 戻り値：
isMirror(root->left, root->right)の結果。
関数 isMirror()：
- まず、現在の左右の2つのノードが対称条件を満たしているか判断します。
- 次に、これら2つのノードの子ノードである
L.leftとR.rightが対称か、またL.rightとR.leftが対称かを判断します。 #再帰 ![[対称二分木.png|697]]