每日算法题【二叉树】：二叉树的最大深度、翻转二叉树、平衡二叉树

(13)二叉树的最大深度

• [104. 二叉树的最大深度 - 力扣（LeetCode）]:

• 解题思路：

  递归思路：二叉树的最大深度等于左右子树中深度大的+1

  /*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*///二叉树的最大深度等于左右子树中深度大的+1
  int maxDepth(struct TreeNode* root) {if (root == NULL) {return 0;}//使用变量保存递归回来的结果进行比较int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;}
  

(14)翻转二叉树

• [226. 翻转二叉树 - 力扣（LeetCode）]:
• 解题思路：翻转每一课树的左右子树根节点

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* flipTree(struct TreeNode* root) {if (root == NULL) {return NULL;}// 交换左右子树struct TreeNode* temp = root->left;root->left = root->right;root->right = temp;// 递归翻转左右子树flipTree(root->left);flipTree(root->right);return root;
}

(15)判断一颗树是否是平衡二叉树

• 110. 平衡二叉树 - 力扣（LeetCode）

• 解题思路：

  要保证当前树的左右子树高度差不大于1，并且子树本身也是平衡树。

  1. maxDepth函数：递归计算二叉树的高度。
  2. isBalanced函数：
     • 如果树为空，返回true
     • 计算左右子树的高度差
     • 如果高度差≤1且左右子树都是平衡的，返回true
     • 否则返回false

  /*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*///二叉树的最大深度等于左右子树中深度大的+1
  int maxDepth(struct TreeNode* root) {if (root == NULL) {return 0;}//使用变量保存递归回来的结果进行比较int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
  }//通过前序遍历二叉树的最大深度来进行判断
  bool isBalanced(struct TreeNode* root) {if(root == NULL){return true;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);//首先要保证当前树的左右子树高度差不大于1，并且子树本身也是平衡树。if(abs(leftDepth - rightDepth)<=1 && isBalanced(root->left) && isBalanced(root->right)){return true;}return false;
  }