题设
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 2 / 3
输出: [1,3,2]
思路
采用递归的方式进行中序遍历，先定义一个中序函数，这个子函数分成四步走，第一步是判断根节点是否为空，如果为空则直接返回，后面三步就是遍历的三个步骤，即递归调用左节点=>列表添加中序结点=>递归调用右节点。然后在母函数里面定义一个空列表，将二叉树的root作为参数调用子函数，最终返回列表即可。
代码
from typing
import List
class TreeNode:
def __init__
(self, val
=0, left
=None, right
=None
):
self.val
= val
self.left
= left
self.right
= right
def list_to_binarytree
(nums
):
if not nums:
return None
root
= TreeNode
(nums
[0
])
queue
= [root
]
i
= 1
length
= len
(nums
)
while i
< length:
node
= queue.pop
(0
)
node.left
= TreeNode
(nums
[i
])
if nums
[i
] is not None:
queue.append
(node.left
)
i +
= 1
if i
< length:
node.right
= TreeNode
(nums
[i
])
if nums
[i
] is not None:
queue.append
(node.right
)
i +
= 1
return root
class Solution:
def inorderTraversal
(self, root: TreeNode
) -
> List
[int
]:
def inorder
(root
):
if not root:
return
inorder
(root.left
)
ans.append
(root.val
)
inorder
(root.right
)
ans
= []
inorder
(root
)
return ans
lst
= [3,9,20,None,None,15,7
]
root
= list_to_binarytree
(lst
)
print
(Solution
().inorderTraversal
(root
))
lst
= [1,None,2,3
]
root
= list_to_binarytree
(lst
)
print
(Solution
().inorderTraversal
(root
))
结果
