题解 | 二叉树的中序遍历

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
class Solution:
    #法1：递归法(左根右)
    # def inorder(self,root:TreeNode,res:List[int]):
    #     if not root:#当根为空时直接返回
    #         return 
    #     else:
    #         self.inorder(root.left,res)#左
    #         res.append(root.val)#根
    #         self.inorder(root.right,res)#右

    # def inorderTraversal(self , root: TreeNode) -> List[int]:
    #     # write code here
    #     res=[]
    #     if not root:#树为空直接返回答案
    #         return res
    #     self.inorder(root,res)
    #     return res

    #法2：根据栈的特性先进后出

    # 1.从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
    # 2：到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。
    def inorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        res,stack = [],[]
        while root or stack:#当栈和当前节点都为空时停止循环

            #深度遍历，直到找到最左的节点，过程中的节点都加入栈中
            while root:
                stack.append(root)#父节点加入栈中
                root=root.left#继续深入左子树

            #取出栈顶元素
            stack_top=stack[-1]
            stack.pop()
            res.append(stack_top.val)

            #直接进入栈顶元素的右边节点，两种情况
            #1.栈顶元素有右子树，接下来会继续循环，
            #遍历该分支直到最左节点，并将过程中的节点加入栈中

            #2.栈顶元素没有右子树，接下来跳过找最左节点的循环，直接取栈顶元素
            root = stack_top.right
        return res