剑指55-II：平衡二叉树

传送门

nowcoder
leetcode

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，只需要考虑其平衡性，不需要考虑其是不是排序二叉树。
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

C++ 代码 - nowcoder

/*
    递归实现
    根据该结点左右子树的高度之差判断是否平衡，然后递归地对左右子树进行判断。
*/
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == nullptr) return true; // 这里返回 true，不是 false
        return abs(maxDepth(pRoot->left) - maxDepth(pRoot->right)) <= 1
               && IsBalanced_Solution(pRoot->left)
               && IsBalanced_Solution(pRoot->right);
    }

    int maxDepth(TreeNode* node) {
        if (node == nullptr) return 0;
        return 1 + max(maxDepth(node->left), maxDepth(node->right));
    }
};

/*
    迭代实现
    这种做法存在的问题：在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。
    若发现子树不是平衡二叉树，则停止遍历。
*/
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == nullptr) return true;
        return getDepth(pRoot) != -1;
    }

    int getDepth(TreeNode* node) {
        if (node == nullptr) return 0;

        int leftDepth = getDepth(node->left);
        if (leftDepth == -1) return -1;
        int rightDepth = getDepth(node->right);
        if (rightDepth == -1) return -1;

        if (abs(leftDepth - rightDepth) > 1) return -1;
        else return 1 + max(leftDepth, rightDepth);
    }
};

C++ 代码 - leetcode

/*
    递归实现
*/
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        return abs(maxDepth(root->left) - maxDepth(root->right)) <= 1
            && isBalanced(root->left)
            && isBalanced(root->right);
    }

    int maxDepth(TreeNode* node) {
        if (node == nullptr) return 0;
        return 1 + max(maxDepth(node->left), maxDepth(node->right));
    }
};

/*
    迭代实现
*/
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        return getDepth(root) != -1;
    }

    int getDepth(TreeNode* node) {
        if (node == nullptr) return 0;

        int leftDepth = getDepth(node->left);
        if (leftDepth == -1) return -1;
        int rightDepth = getDepth(node->right);
        if (rightDepth == -1) return -1;
        if (abs(leftDepth - rightDepth) > 1) return -1;
        else return 1 + max(leftDepth, rightDepth);
    }
};