剑指offer——55.2 平衡二叉树

55.2 平衡二叉树

NowCoder

题目描述

平衡二叉树左右子树高度差不超过 1。

解题思路

/*
（1）非叶子节点最多拥有两个子节点；
（2）非叶子节值大于左边子节点、小于右边子节点；
（3）树的左右两边的层级数相差不会大于1;
（4）没有值相等重复的节点;

***/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int high = getHight(root);
        return high >= 0;
    }
    
    //求平衡二叉树的深度 如果不是平衡二叉树 直接返回-1
    int getHight(TreeNode* root)
    {
        if(!root) return 0;
        int left = getHight(root->left);
        if(left < 0) return -1;
        int right = getHight(root->right);
        if(right < 0) return -1;
        if(abs(left - right) > 1) return -1;
        else return max(left, right) + 1;
    }
};


/*
求二叉树深度 如果深度相差为1 标志false
*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        bool isTrue = true;
        getHigh(root, isTrue);
        return isTrue;
    }
    
    int getHigh(TreeNode* root, bool& isTrue)
    {
        if(!root) return 0;
        int left = getHigh(root->left, isTrue) + 1;
        int right = getHigh(root->right, isTrue) + 1;
        if(abs(left - right) > 1) isTrue = false;
        return max(left, right);
    }
};