Binary Tree Preorder Traversal

Binary Tree Preorder Traversal.png

解題思路 ：

Recursive 方式：
pre-order 基本做法三步驟

1. statements;
2. recursive call (left)
3. recursive call (right)

這邊的 statement 就是把數值存到要回傳的 vector 裡面 當然只處理不是 nullptr 的節點 所以要設定一個 if statement 來檢查

Non - Recursive 方式：
可以使用 stack 只是放入 stack 的順序是 先 right child 然後才放 left child (倒出來才會是正確順序)

C++ code :

<pre><code>
//Recursive:

void preOrder(TreeNode *root, vector<int> &res)

{

if(root != nullptr){ 
    res.emplace_back(root->val);
    preOrder(root->left, res);
    preOrder(root->right, res);
}

}

class Solution {

public:

/**
 * @param root: The root of binary tree.
 * @return: Preorder in vector which contains node values.
 */
vector<int> preorderTraversal(TreeNode *root) {
    // write your code here
    vector<int> res;
    preOrder(root, res);
    return res;
}

};

<code><pre>

//Non - Recursive

class Solution {

public:

/**
 * @param root: The root of binary tree.
 * @return: Preorder in vector which contains node values.
 */
vector<int> preorderTraversal(TreeNode *root) {
    // write your code here
    vector<int> res;
    if(root == nullptr) return res;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty())
    {
        TreeNode *tmp = s.top();
        s.pop();
        res.emplace_back(tmp->val);
        if(tmp->right) s.push(tmp->right);
        if(tmp->left) s.push(tmp->left);
    }
    return res;
}

};