首页>itarticle>leetcode-binary tree inorder traversal
leetcode-binary tree inorder traversal
admin11月 12, 20200
##题目
####Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3},
1
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
####OJ’s Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:
1
/
2 3
/
4
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
1. 如果当前结点的左孩子为空,则输出当前结点并将其当前节点赋值为右孩子。
2. 如果当前节点的左孩子不为空,则寻找当前节点在中序遍历下的前驱节点(也就是当前结点左子树的最右孩子)。接下来分两种情况:
a) 如果前驱节点的右孩子为空,将它的右孩子设置为当前节点(做线索使得稍后可以重新返回父结点)。然后将当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点,表明左子树已经访问完,可以访问当前节点。将它的右孩子重新设为空(恢复树的结构)。输出当前节点。当前节点更新为当前节点的右孩子。
近期评论