目錄

題目描述：

解法一：遞歸法

解法二：迭代法

解法三：Morris 遍歷

二叉樹的前序遍歷

題目描述：

給你二叉樹的根節(jié)點(diǎn)?root?，返回它節(jié)點(diǎn)值的?前序?遍歷。

示例 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]

提示：

• 樹中節(jié)點(diǎn)數(shù)目在范圍?[0, 100]?內(nèi)
• -100 <= Node.val <= 100

解法一：遞歸法

    List<Integer> res = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return res;
        }
        res.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return res;
    }

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)O(n)，其中 nn 是二叉樹的節(jié)點(diǎn)數(shù)。每一個(gè)節(jié)點(diǎn)恰好被遍歷一次。
• 空間復(fù)雜度：O(n)O(n)，為遞歸過程中棧的開銷，平均情況下為 O(\log n)O(logn)，最壞情況下樹呈現(xiàn)鏈狀，為 O(n)O(n)。

解法二：迭代法

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode temp = stack.pop();
            res.add(temp.val);
            if(temp.right != null){
                stack.push(temp.right);
            }
            if(temp.left != null){
                stack.push(temp.left);
            }
        }
        return res;
    }

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)O(n)，其中 nn 是二叉樹的節(jié)點(diǎn)數(shù)。每一個(gè)節(jié)點(diǎn)恰好被遍歷一次。
• 空間復(fù)雜度：O(n)O(n)，為迭代過程中顯式棧的開銷，平均情況下為 O(\log n)O(logn)，最壞情況下樹呈現(xiàn)鏈狀，為 O(n)O(n)。

解法三：Morris 遍歷

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        TreeNode p1 = root, p2 = null;

        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) {
                    res.add(p1.val);
                    p2.right = p1;
                    p1 = p1.left;
                    continue;
                } else {
                    p2.right = null;
                }
            } else {
                res.add(p1.val);
            }
            p1 = p1.right;
        }
        return res;
    }

復(fù)雜度分析文章來源地址http://www.zghlxwxcb.cn/news/detail-416803.html

• 時(shí)間復(fù)雜度：O(n)O(n)，其中 nn 是二叉樹的節(jié)點(diǎn)數(shù)。沒有左子樹的節(jié)點(diǎn)只被訪問一次，有左子樹的節(jié)點(diǎn)被訪問兩次。
• 空間復(fù)雜度：O(1)O(1)。只操作已經(jīng)存在的指針（樹的空閑指針），因此只需要常數(shù)的額外空間。

到了這里，關(guān)于二叉樹的前序遍歷（力扣144）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！