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;
    }
}      

四，解題過程

第一博