LeetCode第589题 – N叉树的前序遍历

63 views

题目

给定一个 N 叉树,返回其节点值的前序遍历。

解答

递归法

	/**
	 * 协助方法,先序遍历节点。
	 * @param node 树节点
	 * @param values 树节点的值的遍历结果
	 */
	public void preorder(Node node, List<Integer> values) {
		if (node == null) {
			return;
		}

		values.add(node.val);
		if (node.children != null) {
			for (Node child : node.children) {
				preorder(child, values);
			}
		}
	}
	/**
	 * 先序遍历的入口方法
	 * @param root 树节点
	 * @return 遍历的结果
	 */
    public List<Integer> preorder(Node root) {
    	if (root == null) {
    		return Collections.emptyList();
    	}

        List<Integer> values = new ArrayList<>();
        preorder(root, values);

        return values;
    }

迭代法

	/**
	 * 先序遍历的入口方法
	 * @param root 树节点
	 * @return 遍历的结果
	 */
    public List<Integer> preorder(Node root) {
    	if (root == null) {
    		return Collections.emptyList();
    	}

    	List<Integer> values = new ArrayList<>();

        LinkedList<Node> nodes = new LinkedList<>();
    	nodes.add(root);

    	while (!nodes.isEmpty()) {
    		Node node = nodes.removeFirst();
    		values.add(node.val);

    		if (node.children != null) {
    			for (int i = node.children.size() - 1; i >= 0; --i) {
    				nodes.addFirst(node.children.get(i));
    			}
    		}
    	}

        return values;
    }

要点
依据树的特点,使用递归法来解题,确实要简洁一些。



若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第589题 – N叉树的前序遍历

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud