大家有没有什么好的写binary tree的心得啊？

crazycodyman 发表于 2019-8-9 11:54
怎么说呢，preorder/inorder/postorder我会用迭代来写一遍，其他统统递归，面试要求我用迭代的话就当没缘 ...

I just read an interesting interview question. Give you the root of a binary tree. find the largest absolute difference from the ancestor and its children. For example
                  5
               /     \
             7        9
                    /     \
                   1      10
in this case, 9 - 1 = 8 is the result. Can you solve it in 20 mintues? Top-down is trivial, can you implement bottom-up? also, can you implement an iterative solution? It is only a medium tag question but I think not everyone could solve it.

WarriorZ 发表于 2019-8-9 13:48
I just read an interesting interview question. Give you the root of a binary tree. find the larges ...

The child not only including left and right child, but also the children of the left or right child.

哈哈哈大家都刷这么多遍吗一遍不够两遍应该能背下来了吧

关键的地方就是， 什么时候走右枝，什么时候走左枝，什么时候停，如何完成剩余的单边树，你需要根据你自己的习惯总结一个模版，这样有助于记忆和提高准确度。

可以一对一交流一下哈哈

刷了第三遍还是没太搞明白的飘过。。。。。。
我已经放弃了， 我想说我先背答案吧。。。。

WarriorZ 发表于 2019-8-9 13:52
The child not only including left and right child, but also the children of the left or right chil ...

bottom up 一脸懵比。。

我觉得遍历的几种方式要熟记于心

iterative 有一种线索化神级遍历方法。。但是一般也不考，主要就那三种顺序遍历来回玩(dfs),最多一个bfs。一般我都从宏观开始看，第一搞清楚函数定义是什么，要做什么。然后你就看，是先处理当前的节点，还是当前节点的处理需要child的结果，然后你就可以写出递归骨架，最后加上base case,也就是递归函数stack最深那层。也就行了。

337845818 发表于 2019-8-9 21:38
可以一对一交流一下哈哈

头像很强。。。