Leetcode 110. 平衡二叉树

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路

• 明确递归函数的参数和返回值：参数是传入的节点指针，返回值是以该节点为根节点的二叉树的高度
• 明确终止条件：遇到空节点返回0,表示以当前节点为根节点的树高度是0
• 明确单层递归逻辑：判断左右子树高度之差，如果差值小于或者等于1,返回当前二叉树的高度

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
// 返回以该节点为根节点的二叉树高度
    int getDepth(TreeNode *node)
    {
    
        if(node == NULL)
        {
    
            return 0;
        }
        int leftDepth = getDepth(node->left);
        if(leftDepth == -1)
        {
    
            return -1;// 说明左子树已经不是平衡二叉树
        }

        int rightDepth = getDepth(node->right);
        if(rightDepth == -1)
        {
    
            return -1;// 说明右子树已经不是平衡二叉树
        }
        return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth,rightDepth);
    }


    bool isBalanced(TreeNode* root) {
    
        return getDepth(root) == -1 ? false:true;
    }
};