题目链接
参考
方法1 递归
image.png
递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
o=[]
def digui(node):
if node:
digui(node.left)
o.append(node.val)
digui(node.right)
digui(root)
return o
方法2 栈
image.png
栈 先进后出的数据结构
因此入栈顺序为右子节点 中 左子节点
这样在出栈 进栈的过程中都是在栈顶进行操作
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
st=[root]
o=[]
if not root :
return o
while(st):
tnode=st.pop()
if isinstance(tnode,TreeNode):
if tnode.right:
st.append(tnode.right)
st.append(tnode.val)
if tnode.left:
st.append(tnode.left)
else:
o.append((tnode))
return o
