题
题号:94
题目:二叉树的中序遍历
难度:简单
链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/
2022/08/23答案
算法思路
本题在课程中是学过的。
大致的思路就是利用迭代。首先是前序、中序、后序的遍历的意思,可以直接通过前/中/后这三个字来理解。前就是第一个遍历根节点(根节点->左子树->右子树),中就是第二个遍历根节点(左子树->根节点->右子树),后就是最后再遍历根节点(左子树->右子树->根节点)。
那样的话,可以通过递归的思想来实现。
当然因为递归对我来说真的是只可意会不可言传(我真的不是特别的能理解递归)。
代码
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""
查看数据
TreeNode{val: 1, left: None, right: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: None}}
"""
if root == None:
return []
li_out = []
li_out = self.inorderTraversal(root.left)
li_out.append(root.val)
li_out.extend(self.inorderTraversal(root.right))
return li_out
结果
思考
让我自己写递归的话,我肯定是不行的。但进阶版貌似是利用迭代?稍后会再行思考。
标签:None,遍历,中序,li,二叉树,节点,root,热题,out From: https://www.cnblogs.com/xiaoaozi/p/16616677.html