- it
- 94
"""
给定一个二叉树，返回它的中序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
"""
from TreeNode
import TreeNode
def inorderTraversal(root
):
temp
= []
def helper(root
):
if not root
:
return
helper
(root
.left
)
temp
.append
(root
.val
)
helper
(root
.right
)
helper
(root
)
return temp
def inorderTraversal(root
):
res
= []
stack
= []
p
= root
while p
or stack
:
while p
:
stack
.append
(p
)
p
= p
.left
p
= stack
.pop
()
res
.append
(p
.val
)
p
= p
.right
return res
root1
= TreeNode
(1)
root2
= TreeNode
(2)
root3
= TreeNode
(3)
root4
= TreeNode
(4)
root5
= TreeNode
(5)
root6
= TreeNode
(6)
root7
= TreeNode
(7)
root8
= TreeNode
(8)
root1
.right
= root2
root1
.left
= root6
root2
.left
= root3
root3
.left
= root4
root3
.right
= root5
root6
.left
= root7
root6
.right
= root8
print(inorderTraversal
(root1
))
