Binary Tree Traversal(Pre,In,Post)(Recursive&Iterative)

Preorder Traversal

原题链接

Given a binary tree, return the preorder traversal of its nodes’ values.

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]

题意:二叉树前序遍历,前序遍历指的是按根-左子树-右子树的顺序遍历一棵二叉树

Recursive

递归做起来非常简单,将值压入vector,然后再递归遍历左子树,右子树

代码如下:

Iterative

非递归需要维护一个栈,并且保证入栈的顺序保持根-左子树-右子树即可,对于当前节点,不断遍历左子树同时压入栈中且保存到结果vector中直到为NULL,然后取栈顶节点,指向右子树

代码如下:

Inorder Traversal

原题链接

Given a binary tree, return the inorder traversal of its nodes’ values.

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]

题意:二叉树中序遍历,中序遍历指的是按左子树-根-右子树的顺序遍历一棵二叉树

Recursive

递归作法与前序遍历类似,不过是将值压入vector操作是在遍历完所有左子树之后

代码如下:

Iterative

非递归作法也与前序遍历类似,不同的是,在遍历完左子树之后才将当前节点值保存到vector中,这样保证了左-根-右的遍历顺序

代码如下:

Postorder Traversal

做完了前序遍历和中序遍历,虽然没有后序遍历的相应题目,当然也还是要了解一下的,后序遍历相对来说是最难的,看了几篇博客学习了一下。

Recursive

递归做法还是ez

代码如下:

Iterative

后序遍历指的是按左子树-右子树-根的顺序遍历一棵二叉树,与此前的前序和中序相比难点在于,遍历完节点的左子树之后,此时栈顶为没有左儿子的节点,但是不能立即输出该节点,因为他还可能存在右儿子,所以要继续搜索完右儿子后该节点再次出现在栈顶,此时才能输出,那么就需要维护某节点是否为第一次出现在栈顶,只有判断为第二次出现时才能输出,那么问题就在于如何判断,即如何保存节点出现情况,最暴力的办法就是记录节点出现的次数,但显然太浪费内存,看到了一个和巧妙的思路,如下:

考虑将每个节点都压入两遍,取出栈顶元素并pop,然后与当前栈顶比较,如果相等,说明该节点还未遍历左右子树,遍历其左右子树并同样压入两遍到栈中,这样以来,如果再次判断该元素不等于当前栈顶,说明他的左右子树已经遍历完毕了,此时就将其输出

代码如下:

发表评论

电子邮件地址不会被公开。