94. 二叉树的中序遍历

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 在leecode中 treenode 默认是一颗树，其中的left、right、val。val 就是我之前经常写的data。
        # 递归方法
        # list_ = []
        # if root!=None:
        #     list_ += self.inorderTraversal(root.left)
        #     list_.append( root.val)
        #     list_ += self.inorderTraversal(root.right)
        # return list_  
        # 循环方法
        list_ = []
        stack = []
        while stack !=[] or root != None:
            while root:
                stack.append(root) 
                root = root.left  
            if stack != []:
                temp_node = stack.pop()
                list_ += [temp_node.val]
                root = temp_node.right 
        return list_