43ce09d5d1771a25de707cddf92683ab
(难度Medium)Problem 94. Binary Tree Inorder Traversal(中序遍历)

链接

Binary Tree Inorder Traversal - LeetCode

难度等级

Medium

题干

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

题意

给定一个棵二叉树,要求返回这棵二叉树中序遍历的结果。

样例

Example:

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

Output: [1,3,2]

题解

二叉树的中序遍历可以说是基础当中的基础了,没什么太多的技术含量。写成递归的形式非常简单:

def dfs(node):
    dfs(node->left)
    ret.append(node->val)
    dfs(node->right)

为什么这么简单呢?因为在我们递归调用的时候,本质上来说编译器会自动为我们生成一个虚拟的栈,存储每一次的调用关系。正因为如此,看似我们只是执行完了一句dfs(node->left),但其实实际上是遍历完成了整个左边的子树。

对于中序遍历来说,整个遍历顺序应该是先遍历完左子树,然后打印当前节点,再遍历当前节点的右子树。

由于虚拟栈的存在,所以我们可以把嵌套调用的事情交给电脑,我们只需要定义节点内的调用顺序即可。

如果想要加深一下印象,那么也可以自己通过实现栈来模拟一下递归调用的过程,本质上来说是一样的。栈顶元素永远是下一次遍历的元素,也就是说我们只需要把下一次需要遍历的节点入栈即可。

```
def search(node):
sk.push(node)
while !sk.empty():
hd = sk.top()
if hd->left != null:
sk.push(hd->left)
// 因为hd的左节点已经入栈了,所以我们把它置空,避免死循环
hd->left = null
// 左子树调用结束之前,不操作当前节点和右子树
continue
print(hd->val)

top Created with Sketch.