首页 > 代码库 > [LeetCode] Binary Tree Preorder Traversal

[LeetCode] Binary Tree Preorder Traversal

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

For example:
Given binary tree {1,#,2,3},

   1         2    /   3

 

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

 

这题简单,属于课本习题的难度,题目提示说用迭代试试,当然用递归也可以AC的。迭代的时候要注意栈的性质,不要push反了。

void preorderIter2(TreeNode *node, stack<TreeNode*>&st, vector<int>&ret) {    while (!st.empty()) {        TreeNode *top = st.top();        st.pop();                ret.push_back(top->val);        if (top->right) st.push(top->right);        if (top->left) st.push(top->left);    }}vector<int> preorderTraversal(TreeNode *root) {    vector<int> ret;    if (!root) return ret;    stack<TreeNode *> st;    st.push(root);    preorderIter2(root, st, ret);    return ret;}

迭代版

void preorderIter(TreeNode *node, vector<int> &ret) {    if (!node) return;    ret.push_back(node->val);    cout << node->val <<endl;    preorderIter(node->left, ret);    preorderIter(node->right, ret);}
迭代

 

[LeetCode] Binary Tree Preorder Traversal