LeetCode_Stack_144. Binary Tree Preorder Traversal 二叉樹的前序周遊【棧，疊代】【簡單】

目錄

一，題目描述

英文描述

中文描述

示例與說明

二，解題思路

三，AC代碼

C++

Java

四，解題過程

第一博

一，題目描述

英文描述

Given the root of a binary tree, return the preorder traversal of its nodes' values.

中文描述

給你二叉樹的根節點 

root

 ，傳回它節點值的 前序 周遊。

示例與說明

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/binary-tree-preorder-traversal

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

二，解題思路

之前做過一題，是關于後序周遊的@&再見螢火蟲&【LeetCode_Stack_145. Binary Tree Postorder Traversal 二叉樹的後序周遊（Java）【棧，疊代】】

主要是借助棧和pre指針。

棧負責記錄節點的路徑，pre記錄上一個周遊的節點（判斷右子樹是否已經周遊過）

三，AC代碼

C++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<TreeNode*> stack;
        vector<int> ans;
        if (root == nullptr) return ans;
        TreeNode* temp = root->left, * pre = nullptr;
        stack.push_back(root);
        ans.push_back(root->val);
        while (!stack.empty()) {
            while (temp != nullptr) {
                stack.push_back(temp);
                ans.push_back(temp->val);
                pre = temp;
                temp = temp->left;
            }
            while (!stack.empty() && (stack.back()->right == nullptr || stack.back()->right == pre)) {
                pre = stack.back();
                stack.pop_back();
            }
            if (!stack.empty()) temp = stack.back()->right;
        }
        return ans;
    }
};
           

Java

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return ans;
        TreeNode pre = new TreeNode(), temp = root.left;
        stack.push(root);
        ans.add(root.val);
        while (!stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                ans.add(temp.val);
                pre = temp;
                temp = temp.left;
            }
            while (!stack.isEmpty() && (stack.peek().right == null || stack.peek().right.equals(pre))) {
                pre = stack.pop();
            }
            if (!stack.isEmpty()) temp = stack.peek().right;
        }
        return ans;
    }
}
           

四，解題過程

第一博

雖然之前做過類似的一題，這次調試細節還是花了很久。。。