56 删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
1->2->3->3->4->4->5
-1->1
-1->1->2->4->4->5
-1->1->2->5
return 1->2->5
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* h)
    {
        auto d = new ListNode(-1);
        d->next = h;
        
        auto p = d;
        while(p->next){
            auto q = p->next;
            //如果有相同的，一直往下找，直到找到不相同
            while(q && p->next->val == q->val) q = q->next;
            
            if(p->next && p->next->next == q) p = p->next;
            else p->next = q;
        }
        
        return d->next;
    }
};

57 二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
根据二叉树中序遍历，可以知道：
（1）如果当前节点有右子树，则右子树中最左侧的节点就是当前节点的后继
（2）如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* p)
    {
        //如果当前节点有右子树，则右子树中最左侧的节点就是当前节点的后继
        if(p->right){
            p = p->right;
            while(p->left) p = p->left;
            return p;
        }
        //如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。
        while(p->next && p == p->next->right) p = p->next;
        return p->next;
    }
};

58 对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
二叉树对称 一定是左孩子与右孩子相反
即左子树的左孩子与右子树的右孩子相等
左子树的右孩子与右子树的左孩子相等
空树也对应空树
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* r)
    {
        return !r || dfs(r->left,r->right);
    }
    bool dfs(TreeNode* p, TreeNode* q){
        // 如果左右孩子有叶结点，那么两个同时都是叶结点
        if(!p||!q)return !p && !q;
        // 左子树的左孩子与右子树的右孩子相等,左子树的右孩子与右子树的左孩子相等
        return p->val == q->val && dfs(p->left,q->right) && dfs(p->right,q->left);
    }
};

59 按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> getVal(vector<TreeNode *> levels){
        vector<int> res;
        for( auto &x : levels)
            res.push_back(x->val);
        return res;
    }
    vector<vector<int> > Print(TreeNode* r) {
        vector<vector<int> > res;
        if(!r)return res;
        vector<TreeNode *> levels;
        levels.push_back(r);
        res.push_back(getVal(levels));
        bool zigzag = true;//奇偶层标志，true为偶数层，false为奇数层
        while(true){
            vector<TreeNode *> newLevels;// 存储每层结点
            for(auto &x : levels){//得到当前层的所有结点
                if(x->left) newLevels.push_back(x->left);
                if(x->right) newLevels.push_back(x->right);
            }
            if(newLevels.size()){//如果还有下一层
                vector<int> temp = getVal(newLevels);//得到当前层的所有结点的值
                if(zigzag)reverse(temp.begin(),temp.end());//如果是偶数层，需要反转，变成从右到左
                res.push_back(temp);//当前层结果存储
                levels = newLevels;//更新level为下一层
            }else break;//没有下一层 直接结束循环
            zigzag = !zigzag;//奇偶层变换
        }
        return res;
    }
    
};

60 把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
二叉树的层序遍历 不用说了吧 用队列
这题的考点是 分层
可以考虑 每次在输出时 先判断这层有几个结点
循环把这些结点输出 就可以往下一层
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* r) {
            vector<vector<int> > res;
            if(!r)return res;
            queue<TreeNode*> q;
            q.push(r);
            while(q.size()){
                int l = 0, r = q.size();//得到当前层的结点个数
                vector<int> ress;
                while(l++ < r){//循环把这些结点输出 就可以往下一层
                    auto x = q.front();
                    q.pop();
                    ress.push_back(x->val);
                    if(x->left)q.push(x->left);
                    if(x->right)q.push(x->right);
                }
                res.push_back(ress);
                
            }
            return res;
        }
    
};