一.二叉树简介

二叉树是每个节点最多有两个子树的树结构，即二叉树中不存在度大于二的节点。并且，二叉树的子树有左右之分，其次序不能颠倒。（其中二叉树还包含完全二叉树和满二叉树）

简单地理解，满足以下两个条件的树就是二叉树： 本身是有序树； 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

二.二叉树特点

二叉树中，第 i 层最多有 2i-1 个结点。 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

三.二叉树前（先）序遍历 

先序遍历的过程： 1.先访问当前节点（即根节点） 2.遍历当前节点的左节点，再同样遍历左子树中的节点 3.遍历完当前节点的左子树后，再去遍历当前节点的右子树，再遍历右子树中的节点 总结：先访问根节点，然后遍历左子树，最后遍历右子树；即根左右

下面画图为大家展示一下遍历过程：

先序遍历结果为：1 2 4 5 3 6 7

可以想象跟着箭头走了一圈，走到的地方就是遍历的节点

先序遍历代码实现：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>stk;
        if(root==nullptr)return res;
        stk.push(root);
        while(!stk.empty()){
            TreeNode*cur=stk.top();//取栈顶元素
            res.push_back(cur->val);//
            stk.pop();//弹出栈顶元素
            if(cur->right){
                stk.push(cur->right);//向栈顶添加元素
            }
            if(cur->left){
                stk.push(cur->left);
            }
        }
    return res;
 }
};

四.二叉树中序遍历

中序遍历的过程： 1.先进入当前节点的左子树，以同样的步骤遍历左子树的节点 2.访问当前节点 3.最后进入到当前节点的右子树，以同样的步骤遍历右子树中的节点 总结： 先遍历左子树，再访问根节点，最后遍历右子树，即 左根右

下面画图为大家展示一下遍历过程：

中序遍历结果为：4 2 5 1 6 3 7

分清楚左子树和根节点还有右子树，按照口令遍历即可

中序遍历代码实现：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
       vector<int>res;
       if(root==nullptr)return res;
       stack<TreeNode*>stk;
       TreeNode*cur=root;
       while(!stk.empty()||cur){
         while(cur){
             stk.push(cur);
             cur=cur->left;
         }
         TreeNode*node=stk.top();
         res.push_back(node->val);
         stk.pop();
         cur=node->right;
       }
       return res;
    }
};

五.二叉树的后序遍历 

后序遍历的过程： 1.先进入当前节点的左子树，以同样的步骤遍历左子树中的节点 2.再进入当前节点的右子树，以同样的步骤去遍历右子树中的节点 3.最后遍历此左子树和右子树的父亲节点，也就是该节点 总结：先遍历左子树，再遍历右子树，最后访问根节点，即左右根

下面画图为大家展示一下遍历过程：

后序遍历结果为：4 5 2 6 7 3 1

按照箭头的顺序走一圈寻找没有子节点或者子节点遍历完的遍历

后序遍历代码实现：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        if(root==nullptr)return res;
        stack<TreeNode*>stk1;
        stack<TreeNode*>stk2;
        stk1.push(root);
        while(!stk1.empty()){
            TreeNode*node=stk1.top();
            stk1.pop();
            stk2.push(node);
            if(node->left){
                stk1.push(node->left);
            }
            if(node->right){
                stk1.push(node->right);
            }
        }
        while(!stk2.empty()){
            TreeNode*cur=stk2.top();
            res.push_back(cur->val);
            stk2.pop();
        }
        return res;
    }
};