1.二叉树的递归非递归遍历

考虑一个完全二叉树 1234567,

先序非递归,打印1,处理2,处理3 直接循环配合一个栈和hashtable,hashtable存储节点的处理方式(打印为false,处理为true);

　　　　　 push(3),hashtable[3]=true;

　　　　　 push(2),hashtable[2]=true;

　　　　　 push(1),hashtable[1]=false;

中序非递归,处理2 ,打印1,处理3 ,直接循环配合一个栈和hashtable,hashtable存储节点的处理方式(打印为false,处理为true)

　　　　　push(3),hashtable[3]=true;

　　　　　push(1),hashtable[1]=false;

　　　　 push(2),hashtable[2]=true;

后序非递归,处理2,处理3,打印1,直接循环配合一个栈和hashtable,hashtable存储节点的处理方式(打印为false,处理为true)

　　　　 push(1),hashtable[1]=false;

　　　　 push(3),hashtable[3]=true;

　　　　 push(2),hashtable[2]=true;

面试手撸3种非递归,不准备,临时自己想,能写得又快又好,要么是大神,要么是记忆里惊人的(很容易忘记的,哎),菜鸡琢磨了半天,终于找到适合自己的路子

2. 打印二叉树的边界(每层最左,最右边,叶子节点)

　 层次遍历,标记节点层数,当访问节点的层数发生变化时候肯定就是边界啦

　 生成最左集合,最右集合,叶子集合,与头结点,然后做个删选排序就行啦

　 时间复杂度O(n),空间复杂度,考虑最坏O(n);

　 先序遍历:

递归的时候传递层数信息,数组标记层数是否访问到(某层首次访问必然是左边界)

　 反向先序遍历,.............................................................................右边界

　 叶子节点集合

3. 线索二叉树,建立索引的规则,时刻.使用线索,先序中序后序遍历二叉树

4.累加和为key的最长搜索序列

　

　

　　

优质内容筛选与推荐>>
1、提高班作品展圆满结束
2、installshiled 创建iis应用程序池和站点
3、html中常用的转义字符总结
4、Zend框架连接数据库的基本处理方式二种方法
5、SVN提示: File or directory '*' is out of date; try updating 解决方案

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中