Home

Morris遍历二叉树

Morris遍历不使用栈,O(1)空间进行二叉树的遍历。 原理就是: 利用叶子结点的右空指针,临时性的指向中序遍历的后继结点。 与这篇文章的想法类似,前序和中序非常相近,顺序是相同的,不同的是访问的时机。 1. 前序、中序遍历 #pseudo code while 结点存在: if 左子树存在: 找到左子树的最右结点, 如果发现左子树的最右结点:#这个最右结点也就是当前结点在中序遍历下的前驱结点 该结点右指针指向当前结点 否则如果最右结点的右指针已经指向当前结点: 还原最右结点的右指针指向NULL else: 访问该结点 转到右...

Read more

由两种遍历结果构造二叉树

还是二叉树遍历的题目,不过是由遍历结果反推二叉树。 Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal 两个题目是类似的,关于树的问题第一反映就是递归。以中序、后序推导为例, 中序结果为LNR,后序结果为LRN,因此可以通过后序结果的最后一个node(即根节点),在中序结果中查找,就可以区分L,R,然后继续递归计算即可。 举个列子,假设二叉树为 1 / \ 2 3 / \ 4 5 中序遍历为 4 2 5 1 3 后序遍历为 ...

Read more

单链表之和

@陈利人在微博上发布了很多有意思的题目,建议大家关注下。 题目地址在这里。 两个单链表(singly linked list),每一个节点里面一个0-9的数字, 输入就相当于两个大数了。然后返回这两个数的和(一个新list)。这两个输入的list 长度相等。 要求是:1. 不用递归。2. 要求算法在最好的情况下,只遍历两个list一次, 最差的情况下两遍。 解答: 第一遍遍历两个链表相加并且存储,第二遍遍历处理节点data >= 10的情况。 如果节点值>10,需要向前进位,需要两个指针,第一个不断迭代链表称为迭代指针,第二个记录需要进位到的节点称为位置指针,此时考虑两种情况: 前一个节点值<9,则前一个节点值+1即可 前一个节点...

Read more

两个有关通配符的问题

一个问题来自leetcode,用于比较一个通配符字符串能否与另一个普通字符串匹配,另一个问题来自英雄会,计算符合通配符字符串比一个普通字符串大的字符串的总个数

Read more