打卡群2刷题总结1009——二叉树的中序遍历

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

# 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 traverse(self, node):
        if not node:
            return
        
        # 左根右
        self.traverse(node.left)
        self.res.append(node.val)
        self.traverse(node.right)
    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.traverse(root)
        return self.res

class Solution:    
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        '''非递归遍历'''
        if not root:
            return []
        stack = [root]
        visit = [0]
        res = []
        while len(stack) > 0:
            # 已经遍历过，将val放到res中
            if visit[-1] == 1:
                res.append(stack.pop().val)
                visit.pop()
            # 未遍历过，则遍历左右节点（由于是栈，先保存右节点，再保存左节点）    
            else:
                node = stack.pop()
                visit_i = visit.pop()
                if node.right:
                    stack.append(node.right)
                    visit.append(0)
                stack.append(node)
                visit.append(1)
                if node.left:
                    stack.append(node.left)
                    visit.append(0)
                
        return res