#94 Binary Tree Inorder Traversal——Top 100 Liked Questions

客官°小女子只卖身不卖艺 2022-01-23 05:15 202阅读 0赞

Given a binary tree, return the *inorder* traversal of its nodes' values.

**Example:**

Input: [1,null,2,3]
       1
        \
         2
        /
       3
    
    Output: [1,3,2]

**Follow up:** Recursive solution is trivial, could you do it iteratively?

> 第一次：递归实现（[https://blog.csdn.net/monster\_ii/article/details/82115772][https_blog.csdn.net_monster_ii_article_details_82115772]）
> 
>     # Definition for a binary tree node.
>     # class TreeNode(object):
>     #     def __init__(self, x):
>     #         self.val = x
>     #         self.left = None
>     #         self.right = None
>     
>     class Solution(object):
>         def inorderTraversal(self, root):
>             """
>             :type root: TreeNode
>             :rtype: List[int]
>             """
>             if not root:
>                 return []
>             res = []
>             res += self.inorderTraversal(root.left)
>             res.append(root.val)
>             res += self.inorderTraversal(root.right)
>             return res
> 
> Runtime: 16 ms, faster than 94.53% of Python online submissions for Binary Tree Inorder Traversal.
> 
> Memory Usage: 11.9 MB, less than 24.93% of Python online submissions for Binary Tree Inorder Traversal.

>  第二次：迭代：
> 
>     # Definition for a binary tree node.
>     # class TreeNode(object):
>     #     def __init__(self, x):
>     #         self.val = x
>     #         self.left = None
>     #         self.right = None
>     
>     class Solution(object):
>         def inorderTraversal(self, root):
>             """
>             :type root: TreeNode
>             :rtype: List[int]
>             """
>             res, stack = [], []
>             while True:
>                 while root:
>                     stack.append(root)
>                     root = root.left
>                 if not stack:
>                     return res
>                 node = stack.pop()
>                 res.append(node.val)
>                 root = node.right
> 
> Runtime: 12 ms, faster than 98.48% of Python online submissions for Binary Tree Inorder Traversal.
> 
> Memory Usage: 11.8 MB, less than 29.40% of Python online submissions for Binary Tree Inorder Traversal.

[https_blog.csdn.net_monster_ii_article_details_82115772]: https://blog.csdn.net/monster_ii/article/details/82115772