题目

标题和出处

标题：二叉树的前序遍历

出处：144. 二叉树的前序遍历

难度

3 级

题目描述

要求

给你二叉树的根结点

root

texttt{root}

root，返回其结点值的前序遍历。

示例

示例 1：

输入：

root

 

=

 

[1,null,2,3]

texttt{root = [1,null,2,3]}

root = [1,null,2,3]
输出：

[1,2,3]

texttt{[1,2,3]}

[1,2,3]

示例 2：

输入：

root

 

=

 

[]

texttt{root = []}

root = []
输出：

[]

texttt{[]}

[]

示例 3：

输入：

root

 

=

 

[1]

texttt{root = [1]}

root = [1]
输出：

[1]

texttt{[1]}

[1]

数据范围

• 树中结点数目在范围 $\text{[0, 100]}$
• $\text{-100}\le \text{Node.val}\le \text{100}$

进阶

递归解法很简单，你可以使用迭代解法完成吗？

解法一

思路和算法

二叉树的前序遍历的方法为：依次遍历根结点、左子树和右子树，对于左子树和右子树使用同样的方法遍历。由于遍历过程具有递归的性质，因此可以使用递归的方法实现二叉树的前序遍历。

递归的终止条件是当前结点为空。对于非终止条件，递归的做法如下。

1. 将当前结点的结点值加入前序遍历序列。

2. 对当前结点的左子树调用递归。

3. 对当前结点的右子树调用递归。

遍历结束之后即可得到前序遍历序列。

代码

class Solution {
    ListInteger> traversal = new ArrayListInteger>();

    public ListInteger> preorderTraversal(TreeNode root) {
        preorder(root);
        return traversal;
    }

    public void preorder(TreeNode node) {
        if (node == null) {
            return;
        }
        traversal.add(node.val);
        preorder(node.left);
        preorder(node.right);
    }
}

复杂度分析

• 时间复杂度：

  O

  (

  n

  )

  O(n)

  O(n)，其中

  n

  n

  n 是二叉树的结点数。每个结点都被访问一次。

• 空间复杂度：

  O

  (

  n

  )

  O(n)

  O(n)，其中

  n

  n

  n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间，取决于二叉树的高度，最坏情况下二叉树的高度是

  O

  (

  n

  )

  O(n)

  O(n)。

解法二

思路和算法

使用迭代的方法实现二叉树的前序遍历，则需要使用栈存储结点。

从根结点开始遍历，遍历的终止条件是栈为空且当前结点为空。遍历的做法如下。

1. 如果当前结点不为空，则将当前结点的结点值加入前序遍历序列，将当前结点入栈，然后将当前结点移动到其左子结点，重复该操作直到当前结点为空。

2. 将一个结点出栈，将当前结点设为出栈结点的右子结点。

3. 重复上述操作，直到达到遍历的终止条件。

代码

class Solution {
    public ListInteger> preorderTraversal(TreeNode root) {
        ListInteger> traversal = new ArrayListInteger>();
        DequeTreeNode> stack = new ArrayDequeTreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                traversal.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop().right;
        }
        return traversal;
    }
}

复杂度分析

• 时间复杂度：

  O

  (

  n

  )

  O(n)

  O(n)，其中

  n

  n

  n 是二叉树的结点数。每个结点都被访问一次。

• 空间复杂度：

  O

  (

  n

  )

  O(n)

  O(n)，其中

  n

  n

  n 是二叉树的结点数。空间复杂度主要是栈空间，取决于二叉树的高度，最坏情况下二叉树的高度是

  O

  (

  n

  )

  O(n)

  O(n)。

解法三

思路和算法

莫里斯遍历是使用常数空间遍历二叉树的方法，由 J. H. Morris 提出。莫里斯遍历的核心思想是利用二叉树的空闲指针维护遍历顺序，达到省略栈空间的目的。

从根结点开始遍历，遍历的终止条件是当前结点为空。

对于每个结点，判断当前结点的左子树是否为空，执行相应的操作。

• 如果当前结点的左子树为空，则将当前结点的结点值加入前序遍历序列，将当前结点移动到其右子结点。

• 如果当前结点的左子树不为空，则找到当前结点的前驱结点，前驱结点为当前结点的左子树中的最右边的结点，判断前驱结点的右子结点是否为空。

  • 如果前驱结点的右子结点为空，则将前驱结点的右子结点设为当前结点，将当前结点的结点值加入前序遍历序列，将当前结点移动到其左子结点。

  • 如果前驱结点的右子结点不为空，则将前驱结点的右子结点设为空，将当前结点移动到其右子结点。

重复上述操作，直到达到遍历的终止条件。

代码

class Solution {
    public ListInteger> preorderTraversal(TreeNode root) {
        ListInteger> traversal = new ArrayListInteger>();
        TreeNode node = root;
        while (node != null) {
            if (node.left == null) {
                traversal.add(node.val);
                node = node.right;
            } else {
                TreeNode predecessor = node.left;
                while (predecessor.right != null && predecessor.right != node) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    predecessor.right = node;
                    traversal.add(node.val);
                    node = node.left;
                } else {
                    predecessor.right = null;
                    node = node.right;
                }
            }
        }
        return traversal;
    }
}

复杂度分析

• 时间复杂度：

  O

  (

  n

  )

  O(n)

  O(n)，其中

  n

  n

  n 是二叉树的结点数。使用莫里斯遍历，每个结点最多被访问两次。

• 空间复杂度：

  O

  (

  1

  )

  O(1)

  O(1)。注意返回值不计入空间复杂度。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: pytest文档 88- pytest-runtime-yoyo 对用例运行时长断言

说明 pytest 执行用例的时候，我们希望对用例的运行时间断言，当用例执行时长大于预期标记此用例失败。@pytest.mark.runtime(1) 运行时长单位是秒 此插件已打包上传到pypi https://pypi.org/project/pytest…