leetcode 144二叉树的前序遍历

1.递归

/**
 * Definition for a binary tree node.
 * 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) {
        
        if(root!=nullptr)
        {
            res.push_back(root->val);
            if(root->left)     //两个if必须在跟节点不为空条件内，否则若根节点为空，继续访问左孩子是错的，因为nullptr没有left
                preorderTraversal(root->left);
            if(root->right)
                preorderTraversal(root->right);
        }
            
        return res;
        
    }
private:
    vector<int> res;
};

2.栈实现（时间复杂度O(n),空间复杂度O(n)）
（1）将根结点入栈
（2）进入循环。先弹出栈顶元素，访问它，然后将该元素的右子树入栈，最后将该元素的左子树入栈。左子树后于右子树入栈保证了左子树先于右子树被访问。
即：取栈顶元素，访问，压右孩子入栈，压左孩子入栈

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        if(root==nullptr)
            return res;
        s.push(root);    //压入根节点
        while(!s.empty())   //栈不空循环
        {
            TreeNode* tmp = s.top(); //取栈顶元素
            res.push_back(tmp->val);
            s.pop(); //弹栈
            if(tmp->right)              //先压右孩子，在入左孩子
                s.push(tmp->right);
            if(tmp->left)
                s.push(tmp->left);
        }
        return res;        
    }
};

还有空间复杂度是O(1)的方法没看
参考
https://leetcode.com/problems/binary-tree-preorder-traversal/discuss/45435/4-solutions-in-c%2B%2B
https://www.jianshu.com/p/890b675a1ac7（有O（1）复杂度的解析）