leetcode 144. Binary Tree Preorder Traversal 二叉树展开为链表(中等)

一、题目大意

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

示例 1:

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

输出:[1,2,3]

示例 2:

输入:root = []

输出:[]

示例 3:

输入:root = [1]

输出:[1]

示例 4:

输入:root = [1,2]

输出:[1,2]

示例 5:

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

输出:[1,2]

提示:

  • 树中节点数目在范围 [0, 100] 内

  • -100 <= Node.val <= 100

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

二叉树的遍历,常见的有先序遍历、中序遍历、后序遍历和层序遍历,它们用uxjv实现起来都非常简单;

考虑使用非递归来实现,用到时stack来辅助转自,由于先序遍历的顺序为 根左右,算法为:

1、把根节点push到栈中

2、循环检查栈是否为空,若不空,取出栈顶元素并保存其值,然后看其右节点是否存在,若存在则push到栈中,再看其左节点,若存在,则push到栈中

三、解题方法

3.1 Java实现-递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 先序遍历:中左右
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }

    void preorder(TreeNode node, List<Integer> ans) {
        if (node == null) {
            return;
        }
        ans.add(node.val);
        preorder(node.left, ans);
        preorder(node.right, ans);
    }
}

3.2 Java实现-迭代

public class Solution2 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        // 使用栈来辅助实现,Java中用双端队列来代替栈
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.addFirst(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            ans.add(tmp.val);
            if (tmp.right != null) {
                stack.addFirst(tmp.right);
            }
            if (tmp.left != null) {
                stack.addFirst(tmp.left);
            }
        }
        return ans;
    }
}

四、总结小记

  • 2022/9/23 遇到“上传下达”的情况,激情顿无,毫无意义

原文链接:https://www.cnblogs.com/okokabcd/p/16722375.html