[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},

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

最新文章

热门文章