search

HZFE / awesome-interview

剑指前端 Offer
http://febook.hzfe.org/
Other
2.32k stars 176 forks source link

平衡二叉树 | HZFE - 剑指前端 Offer #53

Open utterances-bot opened 2 years ago

utterances-bot commented 2 years ago

平衡二叉树 | HZFE - 剑指前端 Offer

题目描述

https://febook.hzfe.org/awesome-interview/book1/algorithm-balanced-binary-trees

joeyLin311 commented 2 years ago

解法二 -> 思路 -> 其中的描述: "上面的方法是自顶而上" , 可能会造成困惑. 解法一中从根节点开始遍历, 直观来看二叉树呈现出来的数据结构形状, 该处写为 "自顶而下" 或者 "从根节点遍历到树的末端" 可能更通顺些

hyperMoss commented 2 years ago

树相关遍历使用yield 性能更好一些，https://www.30secondsofcode.org/articles/s/js-data-structures-binary-tree

xjq7 commented 2 years ago

yield性能好在哪

fpandzc commented 2 years ago

“该方法由于使用了递归，并且每次递归都调用了两次自身，导致会函数栈会按照等差数列开辟", 关于两个算法空间复杂度分析这里，个人认为是O(n),首先从文章的理解来说，等差数列就是一个1+2+4+8+...+2n就也还是一个O(n),其次两个算法当树退化至链表时最差递归空间才到n,也就是从根节点到最后一个节点的栈空间都保存着，空间复杂度怎么也无法到O(n^2)。

xyxiao001 commented 2 years ago

@fpandzc 是的这里的空间复杂度确实是O(n), 空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n

xyxiao001 commented 2 years ago

@Akiq2016 这里应该得修正下