一、二叉树的遍历
二、遍历代码—递归方式
先序遍历：
中序遍历：
后序遍历：
总结发现：先序、中序、后序只是递归序加工的结果
要想遍历所有的节点，每个节点必须经过三次，每次第一次经过时就打印，便是先序遍历；第二次经过时才打印，便是中序遍历；第三次经过时才打印，便是后序遍历。
三、遍历代码—非递归方式
上面代码是通过递归的方式实现遍历，任何递归的方式都可以通过非递归的方式实现，通过栈这种数据结构同样可以实现遍历，本遍提供先序的非递归方式实现，感兴趣的小伙伴可以自己实现下中序和后序遍历，无非是压栈和出栈的顺序怎么调整。
先序的非递归方式实现：
四、二叉树的按层遍历
：
原理：利用队列的数据结构，在遍历第一层的时候，就需要把第二层的非空节点全部入队，以此类推，直到最后一层。
遍历代码：
五、二叉树面试真题解析
题目：；计算二叉树的最大宽度
解析一：利用队列存储节点信息，在遍历当前层的时候，会把下一层的所有节点全部入队，利用数据结构map存储节点的层数信息，key是每个节点，value是其所在的层数。从第一层的根节点开始遍历，每一层遍历结束后，下一层的所有节点完成全部入队，同时在map中存储了节点的层数信息。
**解析二：**不使用map,从第一层的根节点开始遍历，每一层遍历结束后，下一层的所有节点完成全部入队，同时获取到下一层最右边的节点，即当前层的结束节点，依次类推，直到最后一层。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/130193.html
