Google PhD new grad 電面

cups60129 发表于 2018-10-18 03:30
感覺也是一個可以提出來討論的方向~
想了一下感覺要做這點有兩個前提：
1. 可以修改樹的結構

我想的是往上回传的过程中记录树的高度 避免重复call getHeight。 不过面试官看起来想让你在往下传的过程中优化？

Fayeoyaee 发表于 2018-10-18 10:23
我想的是往上回传的过程中记录树的高度 避免重复call getHeight。 不过面试官看起来想让你在往下传的过程 ...

理論上每條樹的path應該都只會traverse一次，在這個問題裡可能不會用上唷~

感觉可以在left right递归操作的时候，除了返回左右子树的高度，同时也返回一个bool值(isBalanced)， 如果isBalanced == false，那么直接返回false，不用再把左右子树的高度全算一遍