Ex55-II 平衡二叉树

题目描述

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

解题思路

原型是后序遍历，从树的叶子节点开始判断是否是平衡二叉树。判断平衡二叉树的基础是确定子树的深度。

代码

class Solution {
 public:
  bool isBalanced(TreeNode *root) {
    int depth = 0;
    return is_balanced_core(root, &depth);
  }

 private:
  bool is_balanced_core(TreeNode *root, int *depth) {
    if (root == nullptr) {
      *depth = 0;
      return true;
    }
    int left_depth = 0, right_depth = 0;
    if (is_balanced_core(root->left, &left_depth) &&
        is_balanced_core(root->right, &right_depth)) {
      int diff = left_depth - right_depth;
      if (diff > 1 || diff < -1) return false;
      *depth = 1 + (left_depth > right_depth ? left_depth : right_depth);
      return true;
    }
    return false;
  }
};

结果

执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了79.86%的用户

内存消耗：21.7 MB, 在所有 C++ 提交中击败了11.02%的用户