树有4种遍历方式，先序遍历，中序遍历，后序遍历(说实话以前一直搞不太清区别，其实这三种遍历都是遵循这么一个规则，基于先序遍历来改变父节点的遍历位置来命名的
先序遍历：父节点，左子树(微观就是左节点)，右子树(微观就是右节点)
中序遍历：左子树，父节点，右子树
后续遍历：左子树，右子树，父节点
层序遍历：从顶向下遍历
先序遍历，中序遍历，后续遍历 的最简单实现方式就是递归(递归对人友好，对计算机不友好)，层序遍历最简单方式是用迭代+队列实现
最近学到了一个技巧，那就是假设处理，比如，遍历链表的时候可以假设头结点和尾节点都是一个已经存在的空元素，这样直接把需要特殊处理的节点给抹除掉了，很大程度简化了逻辑， 以下以最近遇到的后续遍历迭代方式为例子：代码就不贴了，只是聊聊思路，首先根节点可以看成是一个右节点，因为实际遍历就隐含了这么一个意义，此时可以制造一个左节点来和栈顶比较，然后往下遍历。代码写完后，如果你的代码写的不够简洁，比如后续遍历左节点是输出点，有多个地方要输出左节点，此时我称之为代码逻辑与设想不统一，应该思考优化一下，合并成只有一个输出点，真正的优秀的代码应该是语义清晰，逻辑明了 - 技近乎道，大道至简！
最后一个感悟，就是写代码不是最难的，只要能抓住逻辑变化就能写出来，难点在于，怎么发现高效率实现算法，并且证明你的算法实现是正确的？学无止境
网友评论