[数据结构与算法]leetcode每日一题-110:平衡二叉树

leetcode每日一题-110:平衡二叉树

链接

平衡二叉树

题目

分析

遍历树，然后每次判断树的左右两个子树的差值即可。

代码

C++

/**
 * 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:

    bool flag = 1;

    bool isBalanced(TreeNode* root) {
        dfs(root);

        return flag;
    }

    int dfs(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int left = dfs(root->left), right = dfs(root->right);

        if (abs(left - right) > 1) {
            flag = 0;
        }

        return 1 + max(left, right);
    }
};

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

作者：LeetCode-Solution