C++实现LeetCode(110.平衡二叉树)

[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 everynode never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
/ \
9  20
/  \
15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
/ \
2   2
/ \
3   3
/ \
4   4

Return false.

求二叉树是否平衡，根据题目中的定义，高度平衡二叉树是每一个结点的两个子树的深度差不能超过1，那么我们肯定需要一个求各个点深度的函数，然后对每个节点的两个子树来比较深度差，时间复杂度为O(NlgN)，代码如下：

解法一：

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if (!root) return true;
        if (abs(getDepth(root->left) - getDepth(root->right)) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
    int getDepth(TreeNode *root) {
        if (!root) return 0;
        return 1 + max(getDepth(root->left), getDepth(root->right));
    }
};

上面那个方法正确但不是很高效，因为每一个点都会被上面的点计算深度时访问一次，我们可以进行优化。方法是如果我们发现子树不平衡，则不计算具体的深度，而是直接返回-1。那么优化后的方法为：对于每一个节点，我们通过checkDepth方法递归获得左右子树的深度，如果子树是平衡的，则返回真实的深度，若不平衡，直接返回-1，此方法时间复杂度O(N)，空间复杂度O(H)，参见代码如下：

解法二：

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        if (checkDepth(root) == -1) return false;
        else return true;
    }
    int checkDepth(TreeNode *root) {
        if (!root) return 0;
        int left = checkDepth(root->left);
        if (left == -1) return -1;
        int right = checkDepth(root->right);
        if (right == -1) return -1;
        int diff = abs(left - right);
        if (diff > 1) return -1;
        else return 1 + max(left, right);
    }
};

类似题目：

Maximum Depth of Binary Tree

参考资料：

https://leetcode.com/problems/balanced-binary-tree/

https://leetcode.com/problems/balanced-binary-tree/discuss/35691/The-bottom-up-O(N)-solution-would-be-better

https://leetcode.com/problems/balanced-binary-tree/discuss/35686/Java-solution-based-on-height-check-left-and-right-node-in-every-recursion-to-avoid-further-useless-search

到此这篇关于C++实现LeetCode(110.平衡二叉树)的文章就介绍到这了,更多相关C++实现平衡二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(100.判断相同树)

    [LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input:     1     

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary

  • C++实现LeetCode(107.二叉树层序遍历之二)

    C++实现LeetCode(107.二叉树层序遍历之二)

    [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3

  • C++实现LeetCode(104.二叉树的最大深度)

    [LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child

  • C++实现LeetCode(106.由中序和后序遍历建立二叉树)

    [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树 Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given ino

  • C++实现LeetCode(101.判断对称树)

    [LeetCode] 101.Symmetric Tree 判断对称树 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric:     1 / \ 2   2 / \   / \ 3  4 4  3 But the following is not:     1 / \ 2  

  • C++实现LeetCode(102.二叉树层序遍历)

    [LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},     3 / \ 9  20 /  \ 15 

  • C++实现LeetCode(103.二叉树的之字形层序遍历)

    [LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example

  • C++实现LeetCode(110.平衡二叉树)

    [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 everynode never differ by more t

  • C++实现LeetCode(43.字符串相乘)

    [LeetCode] 43. Multiply Strings 字符串相乘 Given two non-negative integers num1 and num2represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6"

  • C++实现LeetCode(89.格雷码)

    C++实现LeetCode(89.格雷码)

    [LeetCode] 89.Gray Code 格雷码 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code se

  • C++实现LeetCode(201.数字范围位相与)

    [LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Credits: Special t

  • C语言平衡二叉树真题练习

    C语言平衡二叉树真题练习

    目录 一.题目描述 二.解题思路 自顶向下的递归(暴力解法) 自底向上的递归(最优解法) 题目难度:简单 LeetCode链接:平衡二叉树 一.题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树. 本题中,一棵高度平衡二叉树定义为:一个二叉树 每个节点 的左右两个子树的高度差的绝对值不超过 1 . 二.解题思路 一棵二叉树是平衡二叉树,当且仅当其所有子树也都是平衡二叉树,因此我们使用递归的方式依次判断其所有子树是否为平衡二叉树,就知道这棵二叉树是不是平衡二叉树了. 自顶向下的递归(暴力解法)

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • oracle中110个常用函数介绍

    1. ASCII 返回与指定的字符对应的十进制数; SQL> select ascii(A) A,ascii(a) a,ascii(0) zero,ascii( ) space from dual; A A ZERO SPACE --------- --------- --------- --------- 65 97 48 32 2. CHR 给出整数,返回对应的字符; SQL> select chr(54740) zhao,chr(65) chr65 from dual; ZH C --

  • C语言 数据结构平衡二叉树实例详解

    C语言 数据结构平衡二叉树实例详解

    数据结构平衡二叉树 参考代码如下: /* 名称:平衡二叉树 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 数据元素个数 typedef char KeyType; /

  • 平衡二叉树的实现实例

    复制代码 代码如下: /*首先平衡二叉树是一个二叉排序树:其基本思想是:在构建二叉排序树的过程中,当每插入一个节点时,先检查是否因为插入而破坏了树的平衡性,若是,找出最小不平衡树,进行适应的旋转,使之成为新的平衡二叉树.*/#include<cstdio>#include<cstdlib>#define LH 1#define EH 0#define RH -1 using namespace std; typedef struct BTNode{ int data; int BF

  • 基于Java实现杨辉三角 LeetCode Pascal's Triangle

    基于Java实现杨辉三角 LeetCode Pascal's Triangle

    Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

随机推荐