struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode( x) : val(x),left(NULL),right(NULL) {}
};

/*二叉树的遍历框架*/
void traverse(TreeNode root)
{
    //前序遍历：先访问根节点，再前序访问左子树，再访问右子树
    traverse(root->left);
    中序遍历：先中序访问左子树，再访问根节点，再访问右子树
    traverse(root->right);
    后续遍历：先后续访问左子树，再访问右子树，再访问根节点
}

class Solution {
public:
    vector<int> result;递归的话定义在这里
    vector<int> preorderTraversal(TreeNode* root) {
        递归方式
        
        if(root == nullptr)
            return {};
        result.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return result;
        */
        当然可以使用迭代解法，因为递归本身就是用栈来实现的，可以通过栈来迭代操作
        但是要注意栈的特性是后入先出，前序的话，就是先放入根节点赋值操作弹出，再放入右节点、左节点，再弹出，这样左节点就会先出，先赋值操作，就是前序了
        stack<TreeNode*> sta;
        vector<int> result;
        sta.push(root);
        while(!sta.empty()) {
            int size = sta.size();
            for(int i=0; i<size; i++) {
                TreeNode* node = sta.top();
                sta.pop();
                result.push_back(node->val);
                if(node->right)
                    sta.push(node->right);
                left)
                    sta.push(node->left);
            }
        }
        return result;
    }
};

*
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0),left(nullptr),right(nullptr) {}
 *     TreeNode(int x) : val(x),right(nullptr) {}
 *     TreeNode(int x,TreeNode *left,TreeNode *right) : val(x),left(left),right(right) {}
 * };
 递归解法定义在这里
    vector<int> postorderTraversal(TreeNode*
        if(root == nullptr)
            return {};
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        result.push_back(root->val);
        return result;
        本题还可以采用迭代解法，因为递归就是用栈来实现的
        考虑实现的过程
        后序遍历是左右中的顺序，但是我们在迭代的时候肯定会先访问根节点，也就是中间的节点，所以考虑先访问和处理中间节点，再处理右节点，再处理左边节点，最后将结果翻转就行了
        stack<TreeNode*>left);
                right);
            }
        }
        reverse(result.begin(),result.end());
         result;
    }
};

vector<int>result;递归写法这里定义
    vector<int> inorderTraversal(TreeNode*递归解法
        if(root == nullptr)
            return {};
        inorderTraversal(root->left);
        result.push_back(root->val);
        inorderTraversal(root->right);
        return result;
        还能采用迭代解法，用栈来解决，因为递归本身就是用栈来实现的，因此是完全行得通的
        中序的顺序是左中右，那出栈的时候，处理的顺序肯定是右中左
        搞清楚访问和处理的概念
        访问：将节点入栈
        处理：将节点的值放入结果集
        中序的访问和处理的顺序是不一样的，所以要借助指针进行访问，也就是将节点放入栈中，用栈来做处理，也就是放入结果集
        vector< result;
        stack<TreeNode*> sta;
        TreeNode* cur = root;
        while(cur != nullptr || !if(cur != nullptr) {指针用来访问节点，访问到左边最底层的时候，指针和要开始处理的位置就一样了
                sta.push(cur);将访问的节点放进栈
                cur = cur->left;最左的子节点最后放进去，所以会先出栈    左
            }
            else {
                cur = sta.top();
                sta.pop();
                result.push_back(cur->val);                             中
                cur = cur->right;                                       右
            }
        }
    }
};

*
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x),right(NULL) {}
 * };
 :
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;创建一个队列，层序遍历树的需要用队列来实现，队列中是二叉树的节点
        if(root != nullptr)
            que.push(root);如果头结点不为空的话，先将头结点放到队列中，因为头结点也就是第一行，只有这一个元素，所以直接放进去
        vector<vector<int>> result;定义返回值，返回的是一个二维数组
        que.empty()) {
            int size = que.size();同一行可能不止一个元素，要循环都进行遍历，又因为下面要进行pop操作，que.size()是一个变化的值，所以这里存储数量
            vector<int> vec;用于临时存储每一行的节点值，最后统一存入返回的二维数组中
             que.front();
                que.pop();//
                vec.push_back(node->left)
                    que.push(node->left);将这个节点的左右子节点放入队列中
                right)
                    que.push(node->right);
            }
            result.push_back(vec);
        }
         result;
    }
};