二叉树，包含：
- 节点元素；
- 指向子节点的指针
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()：
- 先判断当前左右两个节点是否满足对称；
- 再判断这两个节点的子节点
L.left和R.right是否对称，L.right和R.left是否对称。 #递归 ![[对称二叉树.png|697]]