Le défi du pinceau leetcode - Javascript: 110. Arbre binaire équilibré

Tournesol dur 2021-11-25 19:05:01
le fi du pinceau leetcode

R-C.jpeg

「C'est ma participation11Le défi du mois de juin25Oh, mon Dieu.,Voir les détails de l'événement:2021Un dernier défi

Titre

Compte tenu d'un arbre binaire,Pour déterminer si c'est un arbre binaire très équilibré.

Dans cette question,Un arbre binaire équilibré en hauteur est défini comme:

Un arbre binaire par noeud La différence absolue de hauteur entre les sous - arbres gauche et droit de ne pas dépasser 1 .  

Exemple 1:

image.png

Entrée:root = [3,9,20,null,null,15,7]

Produits:true

Exemple 2:

image.png

Entrée:root = [1,2,2,3,3,null,null,4,4]

Produits:false

Exemple 3:

Entrée:root = []

Produits:true

 

Conseils:

  • Le nombre de noeuds dans l'arbre est dans la plage [0, 5000] Intérieur
  • -104 <= Node.val <= 104

Comment résoudre le problème

Méthode 1:De haut en bas(Loi sur la violence)

Comparez la différence maximale de hauteur entre les sous - arbres gauche et droit de chaque noeud de haut en bas , Si la différence maximale de hauteur entre les sous - arbres gauche et droit de chaque noeud de l'arbre binaire est inférieure ou égale à  1 , C'est - à - dire lorsque chaque sous - arbre est équilibré , C'est là que l'arbre binaire est l'arbre binaire équilibré

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * @param {TreeNode} root * @return {boolean} */
var isBalanced = function (root) {
if(!root) return true
return Math.abs(depth(root.left) - depth(root.right)) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right)
}
var depth = function (node) {
if(!node) return -1
return 1 + Math.max(depth(node.left), depth(node.right))
}
Copier le Code

Analyse de la complexité:

  • Complexité temporelle:O(nlogn),Calcul depth  Il y a beaucoup d'opérations redondantes
  • Complexité spatiale:O(n)

Méthode 2: De bas en haut(Optimisation)

En traversant l'arbre binaire par la suite (Gauche et droite), Retour à la hauteur maximale du sous - arbre du Bas au Haut , .Déterminer si chaque sous - arbre est un arbre d'équilibre ,Si l'équilibre, Utilisez leur hauteur pour déterminer si le noeud parent est équilibré , Et calculer la hauteur du noeud parent ,En cas de déséquilibre,Retour -1 .

Parcourez chaque noeud de l'arbre binaire de comparaison La profondeur des sous - arbres gauche et droit :

Comparer les profondeurs des sous - arbres gauche et droit , Si la différence est supérieure à 1 Renvoie une étiquette -1 , Indique que le Sous - arbre actuel est déséquilibré Il y a un sous - arbre à gauche et à droite qui n'est pas équilibré , Ou la différence entre les sous - arbres gauche et droit est supérieure à 1 , Alors l'arbre binaire n'est pas équilibré Si les sous - arbres gauche et droit sont équilibrés , Renvoie la profondeur de l'arbre actuel ( Profondeur maximale des sous - arbres gauche et droit +1 )

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * @param {TreeNode} root * @return {boolean} */
var isBalanced = function (root) {
return balanced(root) !== -1
};
var balanced = function (node) {
if (!node) return 0
const left = balanced(node.left)
const right = balanced(node.right)
if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
return -1
}
return Math.max(left, right) + 1
}
Copier le Code

Analyse de la complexité:

  • Complexité temporelle:O(n)
  • Complexité spatiale:O(n)

Conclusion

Voici Kwai,Il suffit de diriger le cœur vers le soleil,Il y aura de la chaleur~

Attaquons les algorithmes ensemble!!

版权声明
本文为[Tournesol dur]所创,转载请带上原文链接,感谢
https://javamana.com/2021/11/20211125190459871e.html

  1. 图解 Kafka 线程模型及其设计缺陷
  2. Add data files for Oracle tablespaces or temporary tablespaces
  3. Intellij IDEA神器居然还有这些小技巧,mysql集群搭建视频
  4. IntelliJ IDEA(2019)之Web项目创建,掌门一对一java面试题
  5. InnoDB(2,如何访问Redis中的海量数据
  6. InheritableThreadLocal使用详解,java多线程面试题及答案整理
  7. How does Oracle modify the data type of a column
  8. Oracle 12C 12.1.0.1.0 management control file official document translation instructions
  9. Oracle 10g 10.2.0.1 in Oracle Linux 5.4 32bit RAC installation manual (Yimo Xiyang)
  10. Oracle 12C in Oracle Linux 6.5 64bit installation manual
  11. 一天十道Java面试题----第一天(面向对象-------》ArrayList和LinkedList)
  12. Schéma du modèle de fil Kafka et de ses défauts de conception
  13. Starting and shutting down Oracle RAC database cluster
  14. CRS_ Oracle CRS stack is already configured and will be running under init(1M)
  15. Common skills of Oracle stored procedure
  16. Check the number of CPUs, core books and threads of the Linux system
  17. jQuery-实例方法
  18. Oracle de duplicated data
  19. jQuery-dom和jQuery,入口函数(基本知识)
  20. Oracle creates unique constraints on columns that already have duplicate data
  21. JavaScript-拷贝
  22. JavaScript-this指向问题
  23.  There is ^ [[a garbled code problem in the up and down keys in Oracle sqlplus
  24. JavaScript-封装与继承(两种)
  25. JavaScript-包装类型
  26. JavaScript-传值(引用类型,基本类型)
  27. JavaScript-面向对象(构造函数,实例成员,静态成员)
  28. JavaScript-解构赋值
  29. JavaScript-箭头函数
  30. JavaScript-参数
  31. JavaScript-预解析(变量提升)
  32. JavaScript-闭包closure
  33. JavaScript-声明变量的关键字
  34. JavaScript - mot - clé pour déclarer une variable
  35. Fermeture de fermeture JavaScript
  36. JavaScript Pre - parse (promotion des variables)
  37. Paramètres JavaScript
  38. Fonction de flèche JavaScript
  39. JavaScript - déconstruction assignations
  40. Common annotations in springboot
  41. Building CentOS 7.6 with Linux
  42. JavaScript - orienté objet (constructeur, membre d'instance, membre statique)
  43. JavaScript value Transfer (reference type, Basic type)
  44. JavaScript - type d'emballage
  45. linux deepin/ubuntu安装flameshot火焰截图
  46. JavaScript - encapsulation et héritage (deux)
  47. JavaScript JS method for writing 99 multiplication table
  48. 從零開始學java - 第二十五天
  49. Apprendre Java à partir de zéro - jour 25
  50. Les voitures d'hiver, les voitures électriques et les voitures à essence ne sont pas les mêmes?
  51. JavaScript - ceci pointe vers le problème
  52. Copie JavaScript
  53. Spring boot quickly integrates swagger
  54. linux deepin/ubuntu安裝flameshot火焰截圖
  55. Capture d'écran de flamme de l'installateur de flamme Linux deepin / Ubuntu
  56. Jquery DOM et jquery, fonctions d'entrée (bases)
  57. Méthode d'instance jquery
  58. Méthode et démonstration de code dans l'interface de liste en Java
  59. Démarrage du Zookeeper
  60. Java oom Cognition