IterativeDFS [source code]
public class IterativeDFS {
public String iterativeInOrder(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode cur = root;
while (cur != null) {
s.push(cur);
cur = cur.left;
}
while (!s.isEmpty()) {
cur = s.pop();
sb.append(cur.val + " ");
if (cur.right != null) {
cur = cur.right;
while (cur != null) {
s.push(cur);
cur = cur.left;
}
}
}
return sb.toString();
}
public String iterativeInOrder2(TreeNode root) { //more concise version
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode cur = root;
while (cur != null || !s.isEmpty()) {
//push horizontal at the beginning for each node
while (cur != null) {
s.push(cur);
cur = cur.left;
}
cur = s.pop();
sb.append(cur.val + " ");
//choose next node for traversal: null doesn't matter
cur = cur.right;
}
return sb.toString();
}
public String iterativePostOrder(TreeNode root) { //traverse-oriented version
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode cur = root, prev = null;
s.push(root);
while (!s.isEmpty()) {
cur = s.peek();
if (prev == null || prev.left == cur || prev.right == cur) {
if (cur.left != null)
s.push(cur.left); //process left before right
else if (cur.right != null)
s.push(cur.right);
else { //both left and right null
s.pop();
sb.append(cur.val + " ");
}
} else if (cur.left == prev) {
if (cur.right != null)
s.push(cur.right);
else {
s.pop();
sb.append(cur.val + " ");
}
} else if (cur.right == prev) { //this header can be omitted
s.pop();
sb.append(cur.val + " ");
}
prev = cur;
}
return sb.toString();
}
public String iterativePostOrder2(TreeNode root) { //stack-oriented version
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode cur = root, prev = root, next = null;
while (cur != null || !s.isEmpty()) {
while (cur != null) {
s.push(cur);
cur = cur.left;
}
cur = s.peek();
if (cur.right == null || cur.right == prev) {
sb.append(cur.val + " ");
s.pop();
}
if (cur.right == prev)
next = null;
else
next = cur.right;
prev = cur;
cur = next;
}
return sb.toString();
}
public String iterativePreOrder(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
s.push(root);
while (!s.isEmpty()) {
TreeNode cur = s.pop();
while (cur != null) {
sb.append(cur.val + " ");
s.push(cur.right); //tricky: push cur.right rather than cur
cur = cur.left;
}
}
return sb.toString();
}
public String iterativePreOrder2(TreeNode root) { //easier to understand
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
s.push(root);
while (!s.isEmpty()) {
TreeNode cur = s.pop();
sb.append(cur.val + " ");
//push right before left so left is processed after right
if (cur.right != null)
s.push(cur.right);
if (cur.left != null)
s.push(cur.left);
}
return sb.toString();
}
public String morrisInOrder(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
sb.append(cur.val + " ");
cur = cur.right; //cur visited, move on to right
} else {
TreeNode pre = cur.left; //start point is left rather than cur
while (pre.right != null && pre.right != cur) //two termination condition possibilities
pre = pre.right;
if (pre.right == null) { //either: modify
pre.right = cur;
cur = cur.left; //tricky
} else { //or: restore
pre.right = null;
sb.append(cur.val + " ");
cur = cur.right; //again, visit and move on to right
}
}
}
return sb.toString();
}
public String morrisPreOrder(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
sb.append(cur.val + " ");
cur = cur.right; //cur visited, move on to right
} else {
TreeNode pre = cur.left; //start point is left rather than cur
while (pre.right != null && pre.right != cur) //two termination condition possibilities
pre = pre.right;
if (pre.right == null) { //either: modify
pre.right = cur;
sb.append(cur.val + " "); //difference for PreOrder
cur = cur.left; //tricky
} else { //or: restore
pre.right = null;
cur = cur.right; //again, visit and move on to right
}
}
}
return sb.toString();
}
public String morrisPostOrder(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode dump = new TreeNode(0);
dump.left = root;
TreeNode cur = dump;
while (cur != null) {
if (cur.left == null) {
cur = cur.right;
} else {
TreeNode pre = cur.left; //start point is left rather than cur
while (pre.right != null && pre.right != cur) //two termination condition possibilities
pre = pre.right;
if (pre.right == null) { //either: modify
pre.right = cur;
cur = cur.left; //tricky
} else { //or: restore
visitReversed(cur.left, pre, sb);
pre.right = null;
cur = cur.right; //again, visit and move on to right
}
}
}
return sb.toString();
}
public void visitReversed(TreeNode from, TreeNode to, StringBuilder sb) {
if (from == to) {
sb.append(to.val + " ");
return;
}
visitReversed(from.right, to, sb);
sb.append(from.val + " ");
}
// Handles all 3 orders with barely any change at all
public String guidedPreOrder(TreeNode root) {
StringBuilder sb = new StringBuilder ();
Deque<Guide> stack = new ArrayDeque<> ();
stack.push (new Guide (0, root));
while (!stack.isEmpty ()) {
Guide cur = stack.pop ();
if (cur.node == null)
continue; // defensive coding, or leaf handling
if (cur.action == 1) {
sb.append (cur.node.val + " ");
} else {
stack.push (new Guide (0, cur.node.right));
stack.push (new Guide (0, cur.node.left));
stack.push (new Guide (1, cur.node));
}
}
return sb.toString ();
}
public String guidedInOrder(TreeNode root) {
StringBuilder sb = new StringBuilder ();
Deque<Guide> stack = new ArrayDeque<> ();
stack.push (new Guide (0, root));
while (!stack.isEmpty ()) {
Guide cur = stack.pop ();
if (cur.node == null)
continue; // defensive coding, or leaf handling
if (cur.action == 1) {
sb.append (cur.node.val + " ");
} else {
stack.push (new Guide (0, cur.node.right));
stack.push (new Guide (1, cur.node));
stack.push (new Guide (0, cur.node.left));
}
}
return sb.toString ();
}
public String guidedPostOrder(TreeNode root) {
StringBuilder sb = new StringBuilder ();
Deque<Guide> stack = new ArrayDeque<> ();
stack.push (new Guide (0, root));
while (!stack.isEmpty ()) {
Guide cur = stack.pop ();
if (cur.node == null)
continue; // defensive coding, or leaf handling
if (cur.action == 1) {
sb.append (cur.node.val + " ");
} else {
stack.push (new Guide (1, cur.node));
stack.push (new Guide (0, cur.node.right));
stack.push (new Guide (0, cur.node.left));
}
}
return sb.toString ();
}
static class Guide {
// 0 for visit (not print, just pass-by); 1 for print (actually visit this node).
// Another way of thinking: or 1 for actually visit this node, 0 for NOT visit.
int action;
TreeNode node;
Guide (int a, TreeNode n) {
action = a;
node = n;
}
}
public static void main(String[] args) {
TreeNode root = TreeNode.example1;
System.out.printf ("This is the tree: \n%s\n", TreeNode.serialize (root));
IterativeDFS tester = new IterativeDFS();
System.out.println("InOrder");
System.out.println(tester.iterativeInOrder(root));
System.out.println(tester.iterativeInOrder2(root));
System.out.println(tester.morrisInOrder(root));
System.out.println("PostOrder");
System.out.println(tester.iterativePostOrder(root));
System.out.println(tester.iterativePostOrder2(root));
System.out.println(tester.morrisPostOrder(root));
System.out.println("PreOrder");
System.out.println(tester.iterativePreOrder(root));
System.out.println(tester.iterativePreOrder2(root));
System.out.println(tester.morrisPreOrder(root));
System.out.println ("Best");
System.out.println ("preorder:\t" + tester.guidedPreOrder (root));
System.out.println ("Inorder:\t" + tester.guidedInOrder (root));
System.out.println ("Postorder:\t" + tester.guidedPostOrder (root));
}
}
这个是一个专门用来自己实现iterative DFS的程序, 用来练练手;
InOrder其实是比较好写的; 这里iterative给出两个写法; ver1是geeks4geeks上面的写法, ver2是根据discussion上面见到的一个错误PostOrder改写成的InOrder; 注意这里的header, 跟其他的几个的循环header不太一样; 之所以要加一个cur的判断, 是为了让第一个iteration可以顺利开始: 你可能会问, 为什么不干脆就直接一开始把root给push进去? 因为这样root就会被push两次, 就很麻烦了;
好好研究一下这个走大梁的算法, 是可以大概理解这个算法设计的思路的:
- 虽然是iterative的做法, 但是实际上还是有subproblem的概念的, 也就是每一个node是一个iteration;
- 我们要完成InOrder, 要保证的其实就是, 对某一个node, 要保证左边的最先处理, 然后处理node自己, 然后处理右边的; 注意这里的处理不是单纯的visit, 而是apply the itearation code to, 也就是包括一系列的全部操作的一个iteration: 就好像你apply a recursive call to in recursion;
- 左边最先处理的过程, 其实就是用走大梁来完成的. 走大梁的时候, 一个horizontal整个都被push到一个Stack; 因为FILO, 所以当你到达一个node的时候, the immediate node on the same horizontal and to the left of this node, which happens to be just the left child of this node, must be already processed. 所以只要我们保证领node的顺序遵守Stack本身的pop顺序, 那么我们始终是从最左边的位置开始处理; 对应的, 到达某一个node的时候, we can rest assured that everything to the left (and also not above this horizontal level) are already finished;
- 接上面, 当领到一个node的时候, 立刻visit就行了;
- 然后处理右边; 注意这里ver2的优势就体现出来了; 这里ver2我们用一个简单的指针操作, 完成了一个类似recursive call: migration to the next subproblem的过程, 而不是跟ver1那样的话, 这个recursion的过程就不容易看出来;
PostOrder的ver1要注意第一个branch的写法, 这个并不是看起来那么trivial, 并不是BFS里面那种push children那么简单的理解: 这里只有在left是Null的情况下, 才push right; 这个if chain是构成了一个优先级的问题的; 注意, 因为是一个if chain的结构, 所以实际上普通的类似push left before push right so left is processed first的分析也不适用了, 因为在left和right都存在的情况下, 这里其实是只push一个的! 另外这个算法里面, visit操作是可以写的更简单的, 1line, 不过这里还是explicitly写一个pop, 来提醒自己peek和pop结合使用, 或者说delayed/conditional pop技巧的使用;
这里第一个branch的处理其实是关键; 事实上, 如果你理解了, 你可以发现这个branch1的存在导致这个算法其实实际的操作是有推大梁的算法 的, 所以考虑是否可以用类似InOrder ver2的方法写出来一个PostOrder; 见下面, 果然是可以的;
PostOrder的ver2是我自己写的! 我就是按照InOrder的 stack-oriented的思路写的, 虽然写的时候有点麻烦, 不过最后还是搞定了; 关键还是要学会用root level recurison的思路来理解这个iteration; again, 这种思路在这种push beam at the very beginning of each iteration的写法当中最容易理解; 算法本身的话, 理解了还是不难的, 与InOrder不同的是, 当我们领取了一个node之后, 我们不能立刻就pop并且visit, 我们要利用prev来判断是否可以visit了. 如果可以了(右边是prev, 说明finished, 或者右边没东西了), 那么我们就visit并且pop掉;
这个与InOrder比起来稍微难一点的是后面这个traverse next部分的写法: 注意, 这个部分其实对应的就是recursion里面的recursive call, or movement to next subproblem的操作, 当时实际在iteration里面实现起来就变成了对一个temp(指针)的更新; 这里要注意的是, 并不能直接无脑向右走了; 如果我们确定右边已经被visit了, 那么我们就应该主动置Null, 这样可以在下一个iteration的开头触发新的peek操作, 也就是相当于当前的node, 没有任何新的附加操作了, 直接move on to the rest of the stack. 如果说, 我们并不是右边已经visit完成了, 那么我们就直接向右走; 注意, 如果是Null也没有关系的, 下一个iteration开头一个push beam操作之后又会退回来的;
注意, 与ver1类似的是, 我们这里同样使用了prev指针, 以及peek first, then conditional pop的技巧;
这里PreOrder的ver1写法是直接用geeks4geeks上面那个链接里面的PDF里面的伪代码翻译的. 这个代码其实是比较精简的, 注意comment的那一行, push的是right而不是cur自己; 这个代码精简的地方是其实他是非常非常不依赖对Null的判断的; Null的判断全都集合在内部while循环的header上面, 而不是传统做法, 比如push之前判断是否是Null; 这里Stack里面是允许有Null的, 只不过最后pop出来之后被noop而已;
这个代码其实我现在自己仔细看一看, 我觉得其实不是那么trivial的, 并不是我bear笔记上面说的, 只要站在root level recursion的角度上, push right so it's processed later那么简单; 另外这个跟InOrder或者PostOrder的走大梁的算法理解也有区别, 虽然代码看起来很相似; 这里是每一个pop出来的都有一个走大梁的操作; 但是在InOrder他们的做法里面, 我们只有在vertical方向上下潜一步之后, 才开始重新走大梁, 产生一个类似recursion的效果;
当然, 其实这个算法如果你非要用root level recursion的角度来理解其实还是可以的, 一个iteration就是一个node(虽然有Null node, 但是不影响, 直接跳过了), 然后你每一个iteration做的是同样的内容, 也就意味着你对每一个node的操作其实是一样的, 这个跟recursion其实是一个就比较类似的概念了;
PreOrder的ver2其实就是geeks4geeks上面的代码了; 其实跟ver1是很类似的, 但是还是有区别; 其实ver2直接用root level recursion的思路去理解, 才是最好理解的; 而ver1这个有点类似走大梁的思路, 看起来很简单, 实际上理解起来反而难一些; 最好还是自己画一下trace, 你就会理解这个算法的顺序: 从最上面的大梁开始向左走, 每一个node, 先visit, 然后push right(其实就是下一层horizontal对应位置的node, 或者null), 然后继续向左走; 这样也可以大概理解为什么完成了PreOrder, 但是比ver2其实是难理解一些的;
这个是最开始激发我简化geeks4geeks代码的一个在discussion上面看到的错误版本的PostOrder:
public String iterativePostOrderWrong(TreeNode root) { //wrong version of PostOrder
Stack<TreeNode> s = new Stack<>();
StringBuilder sb = new StringBuilder();
TreeNode cur = root, prev = null;
s.push(root);
while (cur != null || !s.isEmpty()) {
while (cur != null) {
s.push(cur);
cur = cur.left;
}
cur = s.peek();
sb.append(cur.val + " ");
if (cur.right != null && prev != cur.right) {
cur = cur.right;
} else {
prev = cur;
s.pop();
cur = null;
}
}
return sb.toString();
}
虽然这个版本本身是错误的, 但是也是激发我优化了现有的算法, 还是很有帮助的; 如果不是这个算法, 我就想不到InOrder和PostOrder的concise版本, 这个版本也是更容易帮助理解root level recursion的版本;
另外关于这种算法的记忆, 我感觉, 直接依赖记代码好像是不现实的, 如果想要真正记忆, 还是要依靠脑子里有一个trace的动画来记忆, 同时配合代码的大体逻辑框架(只记忆trace往往是不足够的); 这两者结合, 我目前感觉好像是最有注意帮助记忆算法的;
原来Morris是可以做到PreOrder和PostOrder的: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
首先, 这里提出InOrder的时间是O(N);
证明时间复杂度为O(n)，最大的疑惑在于寻找中序遍历下二叉树中所有节点的前驱节点的时间复杂度是多少. 直觉上，认为它的复杂度是O(nlgn)，因为找单个节点的前驱节点与树的高度有关。但事实上，寻找所有节点的前驱节点只需要O(n)时间。n个节点的二叉树中一共有n-1条边，整个过程中每条边最多只走2次，一次是为了定位到某个节点，另一次是为了寻找上面某个节点的前驱节点.
注意这里的解释针对的只是找predecessor这个过程, 其实算法的其他部分还是有走某条边的过程的; 首先需要确定的一点是, 外面的大循环的iteration熟练是O(N), 这个是不难理解的, 这个算法核心过程其实就是从threaded binary tree的某个位置开始, 向左走到头, 然后向右直到走到thread的最右边, 这个过程最多是2N.
每一个大iteration里面需要进行一次find predecessor, 所以直观以为, 是不是就是O(N * lgN)了; 但是这里他的分析采用的是一个aggregate的思路; 他认为所有这些大iteration里面用于find predecessor的cost加起来, 其实是O(N);
总体来说他这个证明还是很聪明的, 虽然不是完整的准确, 比如他的证明里面的黑edge其实是不对的, 真正从左到右跳转的时候的right edge是在一开始modify的时候加进去的"虫洞"edge, 所以只有一个edge, 不需要像他画的黑edge那样, 整个从path上面的edge全部都包含进去, 而是直接只有一个edge就行了; anyway, 他的分析总体还是对的;
这个建议具体看一下文章, 解释的很好; 另外回想了一下, N节点的BST有N-1个edge, 这个简单的事实好像我其实都不懂; 感觉有时间还是要总结一下关于BST的这些性质, 基础的变量, 一个是number of nodes, 另外一个是tree height, 因为关于这两个数量, 分别有不同的一些性质总结;
PreOrder的情况, 其实只要改一行代码, 也就是在visit的顺序稍微区别一下就行了;
这个改动看起来很trivial, 不过实际上还是有点巧妙的, 最好还是自己画一个trace看看(网页上有)才能确定真正的运作过程; 事实上, 比如我们到达thread的最左边的时候, visit, 然后向右移动, 这个时候其实下一个iteration是回头的, 只不过因为这个iteration是一个restore的iteration, 所以是silent的, 所以看起来好像没有发生, 但是实际上这个过程非常关键; 不仅是因为它restore了input, 而是如果没有这个restore, 下一步的iteration也会陷入一个死循环;
PostOrder的实现就复杂很多, 这个是作者给出的步骤:
当前节点设置为临时节点dump。
如果当前节点的左孩子为空，则将其右孩子作为当前节点。
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左孩子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右孩子。
重复以上1、2直到当前节点为空。
可以看到, PostOrder的过程跟InOrder是类似的, 这个也是我们以前总结过的一个东西: PreOrder是三种order特殊一点的一个, 而InOrder和PostOrder其实是比较类似的, 他们都要求第一个处理的是left;
这个是作者原来的代码:
void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.
{
if (from == to)
return;
TreeNode *x = from, *y = from->right, *z;
while (true)
{
z = y->right;
y->right = x;
x = y;
y = z;
if (x == to)
break;
}
}
void printReverse(TreeNode* from, TreeNode *to) // print the reversed tree nodes 'from' -> 'to'.
{
reverse(from, to);
TreeNode *p = to;
while (true)
{
printf("%d ", p->val);
if (p == from)
break;
p = p->right;
}
reverse(to, from);
}
void postorderMorrisTraversal(TreeNode *root) {
TreeNode dump(0);
dump.left = root;
TreeNode *cur = &dump, *prev = NULL;
while (cur)
{
if (cur->left == NULL)
{
cur = cur->right;
}
else
{
prev = cur->left;
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
if (prev->right == NULL)
{
prev->right = cur;
cur = cur->left;
}
else
{
printReverse(cur->left, prev); // call print
prev->right = NULL;
cur = cur->right;
}
}
}
}
这个代码跟普通的Morris的InOrder的区别首先是在left null的情况下, 不再visit; 这个倒是有点意外, 因为PreOrder和InOrder的时候, 这种情况下都是要visit的, 而我们又说过实际上PostOrder跟InOrder更加相似;
大概看了一下这个人自己的网页上的trace, 可以说这个算法是非常非常聪明的; 按照这个人的说法, 他是头天晚上学到了Morris, 然后第二天就把这个算法带整个blog都写出来的, 真的非常厉害;
另外他这两个helper其实非常简单, 就是我们在LeetCode里面见过很多次的reverse linked list的要求, 事实上, 你看网页上面的图片就知道了(node被着色代表被visit/print), 你就可以发现他打印的其实是1 linked list at a time, which is constructed by the right child edges of treenodes;
另外他这里这个reverse写的不仅丑, 而且好像还不对:
Morris 后序遍历，翻转链表有问题：
没有处理头结点的右孩子指针，结果会改变二叉链表的结构，影响其他操作。
应该加一句：
from->right = NULL;
这个是一个回复的意见, 我自己纸上画了一下, 好像是有问题, 他这种做法会制造多于的cycle; 不过anyway, 这个reverse linked list本身也不是一个很难的需求, 代码按理来说都可以背出来了;
另外这个算法的复杂度其实还是O(N), 只不过多了一个常数倍数而已: 每个edge被visit的次数增加了;
评论提出, 如果可以无视O(1)空间的要求, 这个PostOrder还是比较好写的:
其实后续遍历一个更简单的方法就是把前序遍历的代码原本access left的地方access right，原本right的地方取left， 并且将原本需要输出的地方入栈。全部走完后最后再出栈print
static void MorrisPostOrder(Node root)
{
if (root == null) return;
var current = root;
var stack = new Stack<int>();
while (current != null)
{
if (current.Right != null)
{
var t = current.Right;
while (t.Left != null && t.Left != current)
{
t = t.Left;
}
if (t.Left == null)
{
stack.Push(current.D);
t.Left = current;
current = current.Right;
}
else
{
t.Left = null;
current = current.Left;
}
}
else
{
stack.Push(current.D);
current = current.Left;
}
}
foreach (var i in stack)
{
Console.Write(i + " ");
}
}
当然, 可以对比这理解这当中的思想就行了而, 如果放弃了O(1)space的要求, Why bother morris in the first place;
Morris这个感觉还是有点难记忆的, 不像Stack做法, 本质上可以直接用recursion来帮助理解; Morris做法很多时候, 尤其是不同order之间的区分的时候, 是很难直接通过代码的逻辑来突然就想到, 哦, 这个顺序对应的就是这个order;
三种order的循环内部的大结构其实是类似的, 需要重点记忆的几个区别在于:
- left null的case的处理; 只有PostOrder的时候这个case是不visit的;
- visit in modify or in restore case; 只有在PreOrder的时候是在modify的时候visit;
另外, 这里这么多iterative的做法, 要记住的一点是, Stack的做法, 基本大header都包含对Stack Empty的判断, 有些concise版本还会加入对cur Null的判断; 但是没有一个Stack做法的大header只有一个对cur Null的判断; 所以一定程度上你也可以说, 所有的Stack做的做法, 本身都是stack-oriented做法, 而cur只不过是每一个iteration开头直接从Stack领过来的而已;
注意, 正是这些Stack-oriented的是我们之前说过的好用root level recursion来理解的做法;
而Morris的做法, header全都是, 而且只有, 对cur Null的判断;