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

(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;
  }