是否是平衡二叉树 110. Balanced Binary Tree

110. Balanced Binary Tree

 

Question Editorial Solution

  My Submissions

• Total Accepted: 124873
• Total Submissions: 357479
• Difficulty: Easy

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Subscribe to see which companies asked this question

class solution {
public:
int dfsHeight (TreeNode *root) {
        if (root == NULL) return 0;

        int leftHeight = dfsHeight (root -> left);
        if (leftHeight == -1) return -1;
        int rightHeight = dfsHeight (root -> right);
        if (rightHeight == -1) return -1;

        if (abs(leftHeight - rightHeight) > 1)  return -1;
        return max (leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode *root) {
        return dfsHeight (root) != -1;
    }
};

以上代码思路是从下到上的去返回结果，这样避免了很多树节点的搜索操作，只有当  左右子树平衡时，返回左右子树的高度差。