【LeetCode】144.二叉树的前序遍历


1.问题

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1

"图1"

输入:root = [1,null,2,3]
输出:[1,2,3]

示例 2

输入:root = []
输出:[]

示例 3

输入:root = [1]
输出:[1]

示例 4

"图2"

输入:root = [1,2]
输出:[1,2]

示例 5

"图3"

输入:root = [1,null,2]
输出:[1,2]

提示

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

2.解题思路

2.1 递归

中序遍历的规则是 根-左-右,然后访问左子树、右子树时同样按照此规则遍历,非常容易通过递归实现,按照规则,代码非常容易写出来。定义 preorderTraversal(root) 为递归遍历函数方法,root 为根节点。伪代码:

root.val;
preorderTraversal(root.left);
preorderTraversal(root.right);

复杂度分析

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

  • 空间复杂度:O(n),为递归过程中栈的开销,平均情况下为 O(log⁡n),最坏情况下树呈现链状,为 O(n)。

2.2 迭代

显示利用栈结构,遍历二叉树。
引用LeetCode动态图解迭代过程:
1)访问根节点

"图4"

2)根节点入栈

"图5"

3)左子树根节点遍历、入栈

"图6"

4)左子树根节点出栈,遍历其左右子节点

"图7"

5)左根节点左子树不存在,遍历其右子树4

"图8"

6)左子树遍历完毕,遍历根节点右子树

"图9"

7)遍历右子树根节点,根节点出栈

"图10"

8)右子树根节点入栈

"图11"

9)右子树左节点遍历,入栈

"图12"

10)右子树左节点遍历完毕,该节点出栈

"图13"

11)遍历右子树右节点,右子树根节点出栈

"图14"

12)右子树右节点遍历,入栈

"图15"

13)右子树遍历完毕,出栈

"图16"

14)遍历完毕

"图17"

复杂度分析

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

  • 空间复杂度:O(n),为迭代过程中显式栈的开销,平均情况下为 O(log⁡n),最坏情况下树呈现链状,为 O(n)。

3.代码

public class Solution {
    /**
     * 递归
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (null == root) {
            return new int[0];
        }
        List<Integer> list = new ArrayList();
        preorderTraversal2(list, root);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
 
 	//递归方法
    public void preorderTraversal2 (List<Integer> list, TreeNode root) {
        if (null == root) {
            return;
        }
        list.add(root.val);
        preorderTraversal2(list, root.left);
        preorderTraversal2(list, root.right);
    }
	
	//迭代,栈思想
	public List<Integer> preorderTraversal(TreeNode root) {
	        List<Integer> res = new ArrayList<>();
	        if (null == root) {
	            return res;
	        }
	        Stack<TreeNode> stack = new Stack<>();
	        stack.add(root);
	        TreeNode p;
	        while (!stack.isEmpty()) {
	            p = stack.pop();
	            res.add(p.val);
	            //先把右节点入栈
	            if (null != p.right) {
	                stack.add(p.right);
	            }
	            if (null != p.left) {
	                stack.add(p.left);
	            }
	        }
	        return res;
	    }
}

文章作者: Kezade
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Kezade !
评论
  目录