当前位置:网站首页>Leetcode brush questions: binary tree 11 (balanced binary tree)
Leetcode brush questions: binary tree 11 (balanced binary tree)
2022-07-05 20:00:00 【Taotao can't learn English】
110. Balanced binary trees
Given a binary tree , Determine if it's a highly balanced binary tree .
In this question , A height balanced binary tree is defined as : Every node of a binary tree The absolute value of the height difference between the left and right subtrees is not more than 1.
Example 1:
Given binary tree [3,9,20,null,null,15,7]
return true .
Example 2:
Given binary tree [1,2,2,3,3,null,null,4,4]
return false .
This question ,,,, So hard , For me, .
The answer is so clever .
Using recursion
It is equivalent to going back up layer by layer , When all are leaf nodes , The height of the tree is 0 + 1 , Otherwise, compare the height of the left and right subtrees of the tree , If the difference > 1, Is an unbalanced binary tree , Otherwise, take the highest tree of the left and right subtrees + Root node Height Is the height of the current tree .
package com.programmercarl.tree;
import com.programmercarl.util.GenerateTreeNode;
import java.util.ArrayDeque;
import java.util.Deque;
/** * @ClassName IsBalanced * @Descriotion TODO * @Author nitaotao * @Date 2022/7/4 11:21 * @Version 1.0 * https://leetcode.cn/problems/balanced-binary-tree/ * 110. Balanced binary trees **/
public class IsBalanced {
/** * Recursive Trilogy * 1. Specify the parameters and return values of recursive functions * Parameters : Current incoming node * Return value : The height of the tree with the current incoming node as the root node * If the binary tree whose current incoming node is the root node is not a balanced binary tree , return -1 * <p> * 2. Specify termination conditions * Null node termination encountered , return 0, Indicates that the height of the tree with this node as the root node of the current node is 0 * <p> * 3. Clarify the logic of single-layer recursion * How to judge the imbalance of left and right subtrees ? * Height difference between left and right subtrees > 1 return -1 * Returns the current height difference * * @param root * @return */
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
// The height is -1 It's not a balanced binary tree
public int getHeight(TreeNode root) {
// The height of empty node is 0
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return - 1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
// Height difference > 1 , Is asymmetric
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
// If the left and right subtrees are balanced binary trees , Returns the overall height of the tree + 1
// The overall height is The height of the current highest subtree + The height of the root node
return Math.max(leftHeight, rightHeight) + 1;
}
}
边栏推荐
- selenium 元素信息
- 【硬核干货】数据分析哪家强?选Pandas还是选SQL
- Is it safe for Anxin securities to open an account online?
- Process file and directory names
- How to apply smart contracts more wisely in 2022?
- Is it safe for CICC fortune to open an account online?
- Debezium series: parsing the default value character set
- leetcode刷题:二叉树10(完全二叉树的节点个数)
- C language OJ gets PE, OJ of ACM introduction~
- [untitled]
猜你喜欢
Elk distributed log analysis system deployment (Huawei cloud)
Inventory of the most complete low code / no code platforms in the whole network: Jiandao cloud, partner cloud, Mingdao cloud, Qingliu, xurong cloud, Jijian cloud, treelab, nailing · Yida, Tencent clo
Database logic processing function
Zhongang Mining: analysis of the current market supply situation of the global fluorite industry in 2022
webuploader文件上传 拖拽上传 进度监听 类型控制 上传结果监听控件
leetcode刷题:二叉树13(相同的树)
Recommended collection, my Tencent Android interview experience sharing
That's awesome. It's enough to read this article
浅浅的谈一下ThreadLocalInsecureRandom
Common - Hero Minesweeper
随机推荐
C#应用程序界面开发基础——窗体控制(5)——分组类控件
深度学习 卷积神经网络(CNN)基础
Parler de threadlocal insecurerandom
[OBS] qstring's UTF-8 Chinese conversion to blog printing UTF-8 char*
Analysis of openh264 decoded data flow
That's awesome. It's enough to read this article
通配符选择器
Inventory of the most complete low code / no code platforms in the whole network: Jiandao cloud, partner cloud, Mingdao cloud, Qingliu, xurong cloud, Jijian cloud, treelab, nailing · Yida, Tencent clo
Zhongang Mining: analysis of the current market supply situation of the global fluorite industry in 2022
ACM getting started Day1
Successful entry into Baidu, 35K monthly salary, 2022 Android development interview answer
再忙不能忘安全
Go language | 03 array, pointer, slice usage
No matter how busy you are, you can't forget safety
IBM has laid off 40 + year-old employees in a large area. Mastering these ten search skills will improve your work efficiency ten times
Thread pool parameters and reasonable settings
Postman core function analysis - parameterization and test report
How to apply smart contracts more wisely in 2022?
Debezium series: modify the source code to support drop foreign key if exists FK
Necessary skills for interview in large factories, 2022android will not die, I will not fall