[LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历

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

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

树的遍历，最常见的有先序遍历，中序遍历，后序遍历和层序遍历，它们用递归实现起来都非常的简单。而题目的要求是不能使用递归求解。

1. 用迭代和stack。2. Morris Traversal Solution

Python: Stack, Time: O(n), Space: O(h) # h is the height of the tree

class Solution2(object):

    def preorderTraversal(self, root):

        """

        :type root: TreeNode

        :rtype: List[int]

        """

        result, stack = [], [(root, False)]

        while stack:

            root, is_visited = stack.pop()

            if root is None:

                continue

            if is_visited:

                result.append(root.val)

            else:

                stack.append((root.right, False))

                stack.append((root.left, False))

                stack.append((root, True))

        return result

Python: Morris， Time: O(n), Space: O(1)

class Solution(object):

    def preorderTraversal(self, root):

        """

        :type root: TreeNode

        :rtype: List[int]

        """

        result, curr = [], root

        while curr:

            if curr.left is None:

                result.append(curr.val)

                curr = curr.right

            else:

                node = curr.left

                while node.right and node.right != curr:

                    node = node.right

                if node.right is None:

                    result.append(curr.val)

                    node.right = curr

                    curr = curr.left

                else:

                    node.right = None

                    curr = curr.right

        return result

类似题目：

[LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历　　

巴特西

[LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历

最新文章

热门文章