[LeetCode]110. Balanced Binary Tree

题目描述

、

思路

深搜
初始化为true
当比较左右子树节点差的绝对值大于1的时候赋值为false

代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* vectorToTree(vector<int> nums){
        if (nums.empty())
            return NULL;
        TreeNode* root = new TreeNode(nums[0]);
        queue<TreeNode*> q;
        q.push(root);

        for (int i = 1; i < nums.size();) {
            int curSize = q.size();
            while (curSize--) {
                TreeNode* node = q.front();
                q.pop();

                if (nums[i]) {
                    node->left = new TreeNode(nums[i]);
                    q.push(node->left);
                }
                else
                    node->left = NULL;
                ++i;
                if (i == nums.size())
                    break;
                if (nums[i]) {
                    node->right = new TreeNode(nums[i]);
                    q.push(node->right);
                }
                else
                    node->right = NULL;
                ++i;
                if (i == nums.size())
                    break;
            }
        }
        return root;
    }

    bool isBalanced(TreeNode* root) {
        maxDepth(root);
        return flag;
    }
    int maxDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        int leftDepth = maxDepth(root->left),
            rightDepth = maxDepth(root->right);
        if (abs(leftDepth - rightDepth) > 1)
            flag = false;
        return max(leftDepth + 1, rightDepth + 1);
    }
private:
    bool flag = true;
};

int main() {
    vector<int> nums = { 1, 0, 1, 1 };
    Solution s;
    TreeNode* root = s.vectorToTree(nums);
    cout << s.isBalanced(root) << endl;

    system("pause");
    return 0;
}