1.二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

思想

有递归和非递归的实现，实现方式也不完全一致，提供比较简单的一种方式。有标准的方法将递归改成非递归。 递归将在另外一篇文章详细写。
前序遍历有个口诀即头左右，我们第一次访问的结点就是当前子树的头结点，所以直接压入栈即可。保证了头结点的最先入栈，我们只需再保证左右子树结点的先后顺序即可。然后我们移动到以该结点为头结点的最左结点，并不断压入栈。我们用这种方式保证了左子树的先处理，只有左子树的结点处理完了，头结点才会出栈，然后按同样方式处理右子树的头结点。

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        auto p = root;//p为遍历点
        while(p||!stk.empty()){
            while(p){//只把左侧链全压入
                ans.push_back(p->val);//根
                stk.push(p);
                p = p->left;
            }
            p = stk.top(),stk.pop();
            p = p->right;
        }
        return ans;
    }

2.二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

思想:

中序遍历的顺序为左头右，我们先保证最左的结点先被处理，只需将从头结点到最左的结点全部压入即可。然后弹出的就是最左结点。我们发现栈里的最左结点的下面一个结点正好是它的头结点，将它弹出栈，然后处理右子树的结点就可以了。

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        auto p = root;//p为遍历点
        stack<TreeNode* > stk;
        while(p || !s.empty()){
            while(p){只把左侧链全压入
                stk.push(p);
                p = p->left;
            }
            p = s.top(),stk.pop();
            ans.push_back(p->val);//根
            p = p->right;//进入右子树
        }
        return ans;
    }

3.二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

思想:

第一种好理解。
第二种的理解。中序遍历的顺序为左头右，我们先保证最左的结点先被处理，只需将从头结点到最左的结点全部压入即可。然后栈顶的就是最左结点。这里设置最近访问结点的原因在于我们不能判断这是访问完左子树返回的还是访问完右子树返回的。如果是访问完左子树返回需要处理右子树，否则不需要。

    1.由前序推后序
    //考虑前序 头左右 想要得到后序 左右头 应该怎么做呢
    //首先可以把前序调整一下 头右左 然后逆序即可得到 左右头 即为后序遍历结果
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode* > stk;
        auto p = root;//遍历点
        while(p||!stk.empty()){//根右左的前序遍历
            while(p){
                ans.push_back(p->val);
                stk.push(p->left);//此处与前序相反 变为右左
                p = p->right;
            }
            p = stk.top();
            stk.pop();
        }
        reverse(ans.begin(),ans.end());//结果逆序即可
        return ans;
    }

    2.直接法，增设最近访问节点,用于判断是从左还是右返回的
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode* > stk;
        TreeNode *p = root,*visited = NULL;//遍历点 最近访问点
        while(p||!stk.empty()){
            while(p){//左侧链全部压入
                stk.push(p);
                p = p -> left;
            }
            p = stk.top();
            if(p->right&&p->right!=visited){//说明p的右边还未访问 需要进入右子树遍历
                p = p->right;
            }
            else {//说明p的右子树访问完毕了 可以输出根p了
                ans.push_back(p->val);//根
                visited = p;
                stk.pop();//该点访问完毕 弹出
                p = NULL;//下次的p将从栈中取得
            }
        }
        return ans;
    }

4.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思想

实际上就是bfs，宽度优先遍历，一层层往下进行。可以不记录每层的结点数，但这有利于下一题的求解。

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<TreeNode* > q;
        q.push(root);
        while(!q.empty()){
            vector<int> levelAns;//保存一层的节点
            int len = q.size();//该层节点数量
            while(len--){
                auto p = q.front();
                q.pop();
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
                levelAns.push_back(p->val);
            }
            ans.push_back(levelAns);
        }
        return ans;
    }

5.二叉树的宽度

求节点数最多的那一层的节点个数。

思想

利用上一题的套路。

    int widthOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int width = 0;
        queue<TreeNode* > q;
        q.push(root);
        while(!q.empty()){
            int len = q.size();//获得该层节点数量
            width = max(width,len);//更新最大宽度
            while(len--){
                auto p = q.front();
                q.pop();
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
        }
        return width;
    }

6.从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思想

前序的顺序是头左右，中序的顺序是左头右，同一个二叉树的前序和后序遍历可以唯一确定这颗二叉树。方法就是整体拆分，前序遍历的第一个结点就是整棵子树的头结点，在中序中找到这个结点，这颗结点之前结点个数的就是左子树的节点个数，右边的就是右子树的结点个数，递归处理头结点，左子树和右子树，将其与前序和中序的序号位置对应。

    unordered_map<int,int> pos;//哈希表 快速查找值的下标
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i++) pos[inorder[i]] = i;//记录值的下标
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){//前序序列的范围 中序序列的范围
        if(pl>pr) return NULL;
        int val = preorder[pl];
        auto root = new TreeNode(val);
        int k = pos[preorder[pl]];//根节点在中序中的位置
        int len =  k - il;//左子树长度
        root->left = dfs(preorder, inorder, pl+1, pl+len, il,k-1);
        root->right = dfs(preorder,inorder, pl+len+1,pr,k+1,ir);
        return root;
    }

7.二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思想

这个算法很简洁，也很漂亮。
首先看边界，有三个边界，即头结点为空，头结点为p,头结点为q。我们要找的是祖先结点，但我们却返回了p和q。这实际上是利用了递归的归的过程，p和q必然是从某一个公共祖先节点，起始是根结点访问的，最先回到的公共头结点就是最近公共祖先。
我们需要子节点p和q的结构位置信息，所以使用后序遍历。当我们查找完左右子树后有四种情况，左空，右空，都空，都不空。如果右边找到了，左边没找到，返回右边。左边同理。没找到就返回空。如果都找到了，那就返回头结点，即为最近公共祖先。可以将其化简为三种。
我们发现返回最近公共祖先的逻辑和返回p，q的逻辑是一致的。即不可能在某个头结点的左子树找到了最近公共祖先，同时在右子树找到p和q，最近公共祖先可以顺利返回。

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //后续遍历思想
        if(!root||root==p||root==q) return root;//p,q节点在根部时
        //p,q节点在子树中时
        auto left = lowestCommonAncestor(root->left,p,q);//左子树的最近祖先
        auto right = lowestCommonAncestor(root->right,p,q);//右
        if(!left){//左子树中不包含p和q，只能是右的返回值
            return right;
        }
        if(!right) return left;//同理
        return root;//此时说明p,q在左右两侧，root就是最近祖先
    }

8.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

思想

轴对称就是f(-x)==f(x)，根节点就是原点，根节点向左移就是-k，向右移就是+k，这样就可以判断是否对称。再结合递归的整体局部分析即可。

    递归
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left,root->right);
    }
    bool dfs(TreeNode* l, TreeNode* r){//判断左右子树l,r是否对称
        if(!l&&!r) return true;
        if(l&&!r||!l&&r) return false;
        if(l->val==r->val){
            return dfs(l->right,r->left)&&dfs(l->left,r->right);
            //左子树的右和右子树的左相同，左子树的左和右子树的右相同时 则对称
        }
        return false;
    }

    非递归
    bool isSymmetric(TreeNode* root) {
    //对左子树采取左中右的中序遍历，对右子树采取右中左的中序遍历，在遍历过程中比较即可
    if(!root) return true;
    stack<TreeNode* > s1,s2;//遍历左子树的栈和遍历右边的栈
    auto p1 = root->left, p2 = root->right;
    while(p1||s1.size()||p2||s2.size()){
        while(p1&&p2){
            s1.push(p1),p1 = p1->left;
            s2.push(p2),p2 = p2->right;
        }
        if(p1||p2) return false;//此时两个本应该都为空的
        p1 = s1.top(), s1.pop();
        p2 = s2.top(), s2.pop();
        if(p1->val!=p2->val) return false;
        p1 = p1->right,p2 = p2->left;
    }
    return true;
}

9.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

思想

结合递归的整体局部分析即可。

    中序遍历为数不多的运用
    long long pre = -1e10;//中序遍历过程中的前驱节点的值
    bool isValidBST(TreeNode* root) {
       if(!root) return true;
       bool t = isValidBST(root->left);
       if(!t||pre>=root->val) return false;//左子树非搜索树或者左子树不小于根 
       pre = root->val;//准备遍历右子树 则当前根作为右子树的前驱节点了
       return isValidBST(root->right);
    }

限定节点值的范围
bool isValidBST(TreeNode* root) {
    return dfs(root,INT_MIN,INT_MAX);
}

bool dfs(TreeNode* p, long long minv, long long maxv){
    if(!p) return true;
    if(p->val<minv||p->val>maxv) return false;//不满足范围则一定不是
    return dfs(p->left,minv,p->val-1ll)&&dfs(p->right,p->val+1ll,maxv);
}

10.平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思想

后序遍历得到子节点的平衡性和高度信息，综合判断，返回结果给父节点。

    bool isBalanced(TreeNode* root) {
        int h = 0;//树的高度
        return dfs(root,h);
    }
    bool dfs(TreeNode* p, int &h){//求出以p为根的树的高度并返回是否平衡
        if(!p) return true;
        int hl = 0, hr = 0;//求出左右子树的高度
        bool lbal = dfs(p->left,hl);
        bool rbal = dfs(p->right,hr);
        h = max(hl,hr)+1;//以p为根的树的高度
        return lbal && rbal && abs(hl-hr)<=1;//左右均平衡且高度差<=1
    }

11.n皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

思想

一种非常简洁但不是很高效的算法。高效的有位运算，分布式计算等。
整体看我们需要枚举每一行的皇后，保证列和对角线不冲突。
局部看枚举最后倒数第二行和最后一行，同时验证正确性。

        for(int i=0;i<n;i++){
            if(check(n-2,i,n)){
                record[n-2]=i;
            for(int i=0;i<n;i++){
	            if(check(n-1,i,n)){
	                record[n-1]=i;
            }
        }
     }
}

把局部抽象成整体，运用同一逻辑，再加上边界即可。

    int count;
    int record[10];
    int totalNQueens(int n) {
        dfs(0,n);
        return count;
    }

    void dfs(int u,int n){
        if(u==n){
            count++;
            return;
        }
        for(int i=0;i<n;i++){
            if(check(u,i,n)){
                record[u]=i;
                dfs(u+1,n);
            }
        }
    }

    bool check(int i,int j,int n){
        for(int k=0;k<i;k++){
            if(abs(i-k)==abs(j-record[k])||record[k]==j) return false;
        }
        return true;
    }

12.树的重心

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输出一个整数，表示删除重心后,所有的子树中最大的子树的结点数目。

思想

后序遍历得到头结点所有子树的结点个数信息，还需要以父节点为根的子树的信息，但不需要再做一次遍历，只需要维护当前结点所有子树总结点个数信息即可得到以父节点为根的子树的结点个数信息，当然需要记得减去自己。
最大值的最小值。就是从n个集合中得到n个最大值，再从n个最大值得到它们的最小值。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = N*2;//因为是无向图 需要存双向边
int h[N],e[M],ne[M],idx;//数组模拟邻接表
int n;
bool st[N];
void add(int a, int b){//插入一条边a->b
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int ans = 0x3f3f3f3f;//
int dfs(int u){//返回以u为根的树的大小
    st[u] = 1;
    int sum = 1,res = 0;//sum是以u为根的子树大小  res是删除u后的连通块内点的个数最大值
    for(int i = h[u]; i != -1; i = ne[i]){//遍历u的所有邻接点
        int j = e[i];//对于u->j这条边
        if(!st[j]){
            int subs = dfs(j);//获得以j为根的子树大小
            res = max(res, subs);
            sum += subs;
        }
    }
    res = max(n-sum,res);//求出删除u后的最大连通块内节点个数
    ans = min(ans,res);//结果值
    return sum;
}
int main(){
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i = 0 ,a,b; i < n-1; i++){
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

13. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

思想

层序遍历二叉树的所有节点，每个结点出队时，将它的左右指针互换，即左右子树交换，同时将左右子树的头结点入队。

    TreeNode* mirrorTree(TreeNode* root) {//层序遍历即bfs
        TreeNode* q[1010];
        if(!root) return root;
        int front=0,rear=-1;
        q[++rear]=root;
        while(front <= rear){
            auto t=q[front++];
            auto temp=t->left;
            t->left=t->right;
            t->right=temp;
            if(t->left) q[++rear]=t->left;
            if(t->right) q[++rear]=t->right;
    }
    return root;
}

14. 验证完全二叉树

验证一棵树是否为完全二叉树。

完全二叉树的定义: 一棵二叉树，除了最后一层之外都是完全填充的，并且最后一层的叶子结点都在左边。

思想

1. bfs层序遍历二叉树，首先根结点入队。
2. 头结点依次出队。
3. 若左右孩子都不为空，将其左右孩子入队。
4. 如果左孩子为空，右孩子不为空，则该树一定不是完全二叉树，返回false。
5. 如果一个结点，左孩子不为空，右孩子为空或者左右孩子都为空，则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则返回false。

    boolean isCBT(TreeNode* root) {
        if (!root) return true;
        TreeNode* q[N];
        int front=0, rear=-1;
        bool leaf = false;
        q[++rear]=root;

        while (front <= rear) {
            auto t = q[front++];
            auto l = t->left;
            auto r = t->right;

            if ((leaf && (l || r)) || (!l && r)) {
                return false;//当前结点不是叶子结点且之前结点有叶子结点 || 当前结点有右孩子无左孩子
            }

            if (l) q[++rear]=l;
            if (r) q[++rear]=r;

            if(!l&&!r) leaf = true;//无孩子即为叶子结点

        }
        return true;
    }