94. 二叉树的中序遍历 [medium]

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

给定一个二叉树，返回它的中序遍历。

示例:

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

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

通过次数186,280 | 提交次数258,731

Forth Try

2020-07-09

按照0145 postorder中的通用写法来一波，果然思路很清晰，其实就跟我最开始用isinstance(node, int)来判断是一样的道理。

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        stack = [root]
        rv = []
        while len(stack):
            node = stack.pop()
            if node:
                if node.right:
                    stack.append(node.right)
                stack.append(node)
                stack.append(None)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                rv.append(node.val)
        return rv 

执行用时：20 ms, 在所有 Python 提交中击败了69.11%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了7.14%的用户

Thrid Try

2020-07-08

这个写法更加模拟了中序dfs递归的程序过程，一般人很难直接写出这个方法，尤其是两个while的操作，还有在初始状态中root不放在stack里，在一般stack出现的环节中很少出现。

看了题解才知道还有这解法，写出了个自己体会的版本。又看了一眼题解，发现写得比我还简单。

另外发现中序遍历的版本，其实就是二叉树的升序排列，不错不错。

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        node = root 
        rv = []
        while node or len(stack):
            # print("stack", stack, "rv", rv)
            while node.left:
                stack.append(node)
                node = node.left 
            rv.append(node.val)
            while len(stack) and not node.right:
                node = stack.pop()
                rv.append(node.val)
            node = node.right 
        return rv 

执行用时：20 ms, 在所有 Python 提交中击败了69.12%的用户
内存消耗：12.6 MB, 在所有 Python 提交中击败了7.14%的用户

参考题解更简略的版本

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        node = root 
        rv = []
        while node or len(stack):
            while node:
                stack.append(node)
                node = node.left 
            node = stack.pop()
            rv.append(node.val)
            node = node.right 
        return rv 

执行用时：20 ms, 在所有 Python 提交中击败了69.12%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了7.14%的用户

Second Try

2020-07-08

跟递归次差不多的写法，但是root得抽离出来才行，不然反复的把left/right node放进去了
其次本来先把root的left和right拿出来，然后把root.left和root.right都设置为None, 但是破坏了节点本身，太低级
所以最后直接把value放进去，但是拿出来的时候要判断一些
这种情况遇到强类型语言就有点难办，毕竟stack本身是存储node的，怎么能变成存储int呢

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        seq = []
        stack = [root]
        while len(stack):
            """

            """
            root = stack.pop()
            if root and isinstance(root, TreeNode):
                stack.append(root.right)
                stack.append(root.val)
                stack.append(root.left)
                # stack.append(root.right)
                # stack.append(root)
                # stack.append(root.left)
            if root and isinstance(root, int):
                seq.append(root)
        return seq 

执行用时：24 ms, 在所有 Python 提交中击败了42.21%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了7.14%的用户

First Try

2020-07-08

终于了解了什么是中序遍历，其实就是把一棵树垂直投影，从左到右排列出来就是了。对于每个分支，都按照 node.left -> node -> node.right打印出来。

本来看题目的示例，完全看不出来是怎么排出来的。既然已经知道了含义，那么深度递归法就很方便了。先处理左边，再中间，然后右边。

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        seq = []
        def idfs(root):
            if root:
                idfs(root.left)
                seq.append(root.val)
                idfs(root.right)
        idfs(root)
        return seq 

执行用时：24 ms, 在所有 Python 提交中击败了42.21%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了7.14%的用户

94. 二叉树的中序遍历 [medium]​

Forth Try​

Thrid Try​

Second Try​

First Try​

94. 二叉树的中序遍历 [medium]

Forth Try

Thrid Try

Second Try

First Try