专栏首页计算机视觉与深度学习基础Leetcode 110 Balanced Binary Tree

Leetcode 110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

判断树是否是平衡的。

注意平衡树的定义,每一个点的左右子树高度差不超过1,并不是叶子结点的最大深度和最小深度不超过1.

/**
 * 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:
    int dfs(TreeNode* root,bool& res)
    {
        if(!root) return 0;
        int a=dfs(root->left,res)+1;
        int b=dfs(root->right,res)+1;
        if(abs(a-b)>1) res=false;
        return max(a,b);
    }
    bool isBalanced(TreeNode* root) {
        bool res=true;
        dfs(root,res);
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 230. Kth Smallest Element in a BST

    Given a binary search tree, write a function kthSmallest to find the kth small...

    triplebee
  • Leetcode 144 Binary Tree Preorder Traversal

    Given a binary tree, return the preorder traversal of its nodes' values. For e...

    triplebee
  • Leetcode 145 Binary Tree Postorder Traversal

    Given a binary tree, return the postorder traversal of its nodes' values. For ...

    triplebee
  • Leetcode 230. Kth Smallest Element in a BST

    Given a binary search tree, write a function kthSmallest to find the kth small...

    triplebee
  • Leetcode 145 Binary Tree Postorder Traversal

    Given a binary tree, return the postorder traversal of its nodes' values. For ...

    triplebee
  • Leetcode 144 Binary Tree Preorder Traversal

    Given a binary tree, return the preorder traversal of its nodes' values. For e...

    triplebee
  • 【leetcode刷题】T130-二叉搜索树中第K小的元素

    https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

    木又AI帮
  • 算法篇:树之倒数k个节点

    这类题目的核心思想是,利用二叉树的中序遍历是从小到大的,将其转变成数组,然后对这个有序数组进行取值操作就可以了。

    灰子学技术
  • 算法篇:树之树的层次遍历

    树的层次遍历是树的基本操作之一,包括二叉树的层次遍历,多叉树的层次遍历,以及二叉树层次遍历的变形题目,层次遍历+每一层的节点的翻转等操作。

    灰子学技术
  • LintCode 二叉树的最小深度题目代码

    desperate633

扫码关注云+社区

领取腾讯云代金券