144. 二叉樹的前序遍歷

難度簡單

1088

給你二叉樹的根節(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

?

進(jìn)階：遞歸算法很簡單，你可以通過迭代算法完成嗎？

代碼：

/**

?*?Definition?for?a?binary?tree?node.

?*?struct?TreeNode?{

?*?????int?val;

?*?????TreeNode?*left;

?*?????TreeNode?*right;

?*?????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}

?*?????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}

?*?????TreeNode(int?x,?TreeNode?*left,?TreeNode?*right)?:?val(x),?left(left),?right(right)?{}

?*?};

?*/

class?Solution?{

public:

????vector<int>?preorderTraversal(TreeNode*?root)?{

????????stack<TreeNode*>?sub;

????????vector<int>?ans;

????????if(root==nullptr)return?ans;

????????sub.push(root);

????????while(!sub.empty()){

????????????TreeNode?*temp?=?sub.top();

????????????sub.pop();

????????????ans.push_back(temp->val);

????????????if(temp->right)sub.push(temp->right);

????????????if(temp->left)sub.push(temp->left);

????????}

????????return?ans;

????}

};