Leetcode

非递归遍历二叉树

非递归遍历二叉树

先根遍历

对于递归来说，有一个很大的特征，就是先访问到的函数需要越晚结束掉。因此这就对应上栈这种数据结构。对于先根遍历来说递归函数是这样写的

1
2
3
4
5
dg(root){
    fangwen(root);
    dg(root->left);
    dg(root->right);
}

每次都需要把root入栈，因为只有这样才能找到左右儿子。因此对于当前节点P，先对其进行访问，然后把P入栈，然后再去访问P的左儿子，等到左儿子全都访问完毕后，会从栈里弹出P，从而找到右儿子。因此，有左儿子的情况下，需要把P入栈（之前访问过了），然后将P设为左儿子，从而进入左子树。

如果没有左儿子的话，就去看右儿子，由于已经找到右儿子，所以就不需要把当前节点P入栈了，直接将P设成当前节点的右儿子。

如果没有右儿子的话，则继续弹出，直到有右儿子为止，或者栈弹空了。

中根遍历

递归的写法

1
2
3
4
5
dg(root){
    dg(root->left);
    fangwen(root);
    dg(root->right);
}

可以看出来，我们将root也就是P放进栈，是为了到时候拿出来进行访问，并且需要从而进入右儿子。

对于当前节点P，如果它有左子树的话，则将其入栈，并且将P=P->left

如果它没有左子树，则对其进行访问。如果有右子树，则将P设置为P=P->right。如果也没有右子树的话，则从栈里再弹出一个元素，并设置为P。

后根遍历

递归的写法

1
2
3
4
5
dg(root){
    dg(root->left)
    dg(root->right)
    fangwen(root);
}

入栈是为了找到右子树和访问中间节点。因此只有第二次出现在栈顶的时候（进去的时候不算）才能被弹出，第一次是为了找到右节点，第二次是为了访问。

因此对于当前的P，如果它有左子树，则将其P->record=0，然后P=P->left，如果没有左子树，则将其P->record=1，然后P=P->right。record=0表示还没出现在栈顶过，如果是1则表示左边已经不需要考虑，发现等0则不需要弹栈，如果等1，则需要弹栈

无左有右的情况下，需要把record设为1，然后将当前节点设置为P=P->right

无左无右的情况下，直接访问当前节点，然后弹出一个。如果P->record=1，则访问这个P，然后接着弹，直到一个P->record==0或者弹空，等0的时候，则将其设置为1，再放入栈里，然后再将P设置为它的右儿子。

分享到