首页 > 代码库 > leetcode Binary Tree Preorder Traversal

leetcode Binary Tree Preorder Traversal

实现前序遍历。可参见中序遍历Binary Tree Inorder Traversal

递归:

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    void helper144(TreeNode *root, vector<int> &perm)    {        if (!root) return;        perm.push_back(root -> val);        helper144(root -> left, perm);        helper144(root -> right, perm);    }    vector<int> preorderTraversal(TreeNode *root)     {        vector<int> perm;        helper144(root, perm);        return perm;    }};

 

非递归:

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector<int> preorderTraversal(TreeNode *root)     {        vector<int> perm;        stack<TreeNode *> sta;        TreeNode *p = root;                while(!sta.empty() || p)        {            while(p)            {                perm.push_back(p->val);                if (p -> right)                    sta.push(p -> right);                p = p -> left;            }            if (!sta.empty())            {                p = sta.top();                sta.pop();            }        }        return perm;    }};

 

leetcode Binary Tree Preorder Traversal