首页 > 代码库 > [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?

题意

先序遍历二叉树,递归的思路是普通的,能否用迭代呢?

非递归思路:<借助stack>

    vector<int> preorderTraversal(TreeNode *root) {        stack<TreeNode* > st;        vector<int> vi;        vi.clear();        if(!root) return vi;                st.push(root);        while(!st.empty()){            TreeNode *tmp = st.top();            vi.push_back(tmp->val);                st.pop();            if(tmp->right) st.push(tmp->right);            if(tmp->left) st.push(tmp->left);        }        return vi;    }

递归思路:

class Solution {private:    vector<int> vi;public:    vector<int> preorderTraversal(TreeNode *root) {        vi.clear();        if(!root) return vi;        preorder(root);return vi;    }    void preorder(TreeNode* root){        if(!root) return;        vi.push_back(root->val);        preorder(root->left);        preorder(root->right);    }};

-------------------------------------------------

作者:Double_Win

出处: http://www.cnblogs.com/double-win/p/3895822.html 

声明: 由于本人水平有限,文章在表述和代码方面如有不妥之处,欢迎批评指正~