给定一个二叉树，返回它的 前序 遍历。

c plus

  • 递归法

    1. class Solution {
    2. public:
    3.   vector<int> res;
    4.   vector<int> preorderTraversal(TreeNode* root) {
    5.       helper(root);
    6.       return res;
    7.   }
    8.   void helper(TreeNode * root) {
    9.       if (root == NULL) return;
    10.       res.push_back(root->val);
    11.       helper(root->left);
    12.       helper(root->right);
    13.   }
    14. };

  • 迭代法
    先访问根节点，即先将根节点存入结果，然后将右节点放入栈中，待访问完左子树后,you出栈访问。

    1. class Solution {
    2. public:
    3.   vector<int> preorderTraversal(TreeNode* root) {
    4.       vector<int> res;
    5.       stack<TreeNode *>s;
    6.       TreeNode *rt = root;
    7.       while (rt || s.size())
    8.       {
    9.           while (rt) {
    10.               res.push_back(rt->val);      
    11.               s.push(rt->right);
    12.               rt = rt->left;
    13.           }
    14.           rt = s.top();s.pop();
    15.       }
    16.       return res;
    17.   }
    18. };

%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%8C%E8%BF%94%E5%9B%9E%E5%AE%83%E7%9A%84%20%E5%89%8D%E5%BA%8F%20%E9%81%8D%E5%8E%86%E3%80%82%0A%0A%23%23%23%20c%20plus%0A%0A%0A%0A%20%E9%80%92%E5%BD%92%E6%B3%95%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20vector%3Cint%3E%20res%3B%0A%20%20%20%20vector%3Cint%3E%20preorderTraversal(TreeNode%20root)%20%7B%0A%20%20%20%20%20%20%20%20helper(root)%3B%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%20%20%20%20void%20helper(TreeNode%20%20root)%20%7B%0A%20%20%20%20%20%20%20%20if%20(root%20%3D%3D%20NULL)%20return%3B%0A%20%20%20%20%20%20%20%20res.push_back(root-%3Eval)%3B%0A%20%20%20%20%20%20%20%20helper(root-%3Eleft)%3B%0A%20%20%20%20%20%20%20%20helper(root-%3Eright)%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%0A%60%60%60%0A%0A*%20%E8%BF%AD%E4%BB%A3%E6%B3%95%0A%E5%85%88%E8%AE%BF%E9%97%AE%E6%A0%B9%E8%8A%82%E7%82%B9%EF%BC%8C%E5%8D%B3%E5%85%88%E5%B0%86%E6%A0%B9%E8%8A%82%E7%82%B9%E5%AD%98%E5%85%A5%E7%BB%93%E6%9E%9C%EF%BC%8C%E7%84%B6%E5%90%8E%E5%B0%86%E5%8F%B3%E8%8A%82%E7%82%B9%E6%94%BE%E5%85%A5%E6%A0%88%E4%B8%AD%EF%BC%8C%E5%BE%85%E8%AE%BF%E9%97%AE%E5%AE%8C%E5%B7%A6%E5%AD%90%E6%A0%91%E5%90%8E%2C%E5%8F%B3%E5%AD%90%E6%A0%91%E5%87%BA%E6%A0%88%E8%AE%BF%E9%97%AE%E3%80%82%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20vector%3Cint%3E%20preorderTraversal(TreeNode%20root)%20%7B%0A%20%20%20%20%20%20%20%20vector%3Cint%3E%20res%3B%0A%20%20%20%20%20%20%20%20stack%3CTreeNode%20%3Es%3B%0A%20%20%20%20%20%20%20%20TreeNode%20rt%20%3D%20root%3B%0A%20%20%20%20%20%20%20%20while%20(rt%20%7C%7C%20s.size())%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(rt)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res.push_back(rt-%3Eval)%3B%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s.push(rt-%3Eright)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rt%20%3D%20rt-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20rt%20%3D%20s.top()%3Bs.pop()%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%0A%60%60%60%0A%0A