题解 | #二叉树的前序遍历#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */

    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        stack<TreeNode*> ST;
        vector<int> vec;
        if(root){
            ST.push(root);
        }
        while(!ST.empty()){
            TreeNode *node =ST.top();
            //当前栈顶
            ST.pop();
                vec.push_back(node->val);
                //存放栈顶元素
            if(node->right){
                ST.push(node->right);
            } 
            if(node->left){
                ST.push(node->left);
            }   

            //因为栈，先进后出，根左右，要想在处理完根后先处理左，那么就是先把右压进栈。
        }
        return vec;

      


    }
};

非递归法，用栈和vector容器。

    if(root){
        ST.push(root);
    }

先处理根。入栈。

while(!ST.empty()){
            TreeNode *node =ST.top();
            //当前栈顶
            ST.pop();
      vec.push_back(node->val);
                //存放栈顶元素
            if(node->right){
                ST.push(node->right);
            } 
            if(node->left){
                ST.push(node->left);
            }   
            //因为栈，先进后出，根左右，要想在处理完根后先处理左，那么就是先把右压进栈。
        }
        return vec;

在处理之时，此时栈内元素是根，如何处理，前序根左右，先存根， TreeNode *node =ST.top(); vec.push_back(node->val);放入vector;然后出栈 ST.pop(); 接下来要处理左支，当时栈的特殊性，先入栈左支节点的话，那就是压在了右支节点的下面，取不出来。要想先处理左支，还是得先入栈右支。先出栈左支先存。按此逻辑下去，当处理左支的时候，左支的根节点出栈存vector，需要判断左支节点是否有左右孩子，如果有还是需要按照根左右，先入栈。一层层下去。直到叶子节点，没有左右孩子时。那么此时叶子节点存vector后出栈，没有孩子节点没有入栈。这次就是返回到上一次。看栈中的当前栈顶元素。一般是两种情况，一种是，叶子节点的兄弟节点，也就是右节点，此时仍然按照根左右进行。另一种，当前叶子就是父节点的右节点。那么说明当前叶子的父节点这一支都已经遍历完成，可以向上，父节点的兄弟节点或者更上一层。