剑指offer＜数据结构＞---------------二叉树Ⅲ

二叉搜索树与链表

题目来源：牛客网

1、问题描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

2、思路解析

思路：中序遍历+双指针
定义两个指针一个为链表的头节点，一个指向链表的为节点。已知搜索树的中序遍历为一组有序的数组，所以中序遍历才能将所有节点连接起来，才能形成一个有序的链表。
（1）递归搜索树的左子树的直到递归到最左边的节点，将最左边的节点插入到链表的头节点，使链表的头尾指针指向同一个节点
（2）向上回溯，回溯到上边的一个节点将节点插入到尾指针处，再将尾指针指向最后一节点。
（3）递归搜索树的右子树直到递归完搜索树的所有节点

3、代码实现

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public://双指针
    TreeNode*head=NULL;
    TreeNode*cur=NULL;
    
    TreeNode*Convert(TreeNode* root){if(root==NULL){returnNULL;}//中序遍历Convert(root->left);//到达最左边的节点if(head==NULL){
            head=root;
            cur=root;}else{//将新节点连接到尾节点上
            cur->right=root;
            root->left=cur;
            cur=root;}Convert(root->right);return head;}};

判断是不是平衡二叉树

题目来源：牛客网

1、问题描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

2、思路解析

思路：递归+树的最大深度
先确定递归的结束条件就是节点为NULL说明在当前节点处这个子树就是一个平衡树，然后求左子树和右子树的最大深度的差值，如果差值大于1就说明这不是一颗平衡树直接返回false，递归同时判断左子树和右子树是不是平衡树，同时满足使根节点为当前节点的子树才是平衡树

3、代码实现

class Solution {
public:intDepth(TreeNode*root){if(root==NULL){return0;}returnmax(Depth(root->left)+1,Depth(root->right)+1);}
    bool IsBalanced_Solution(TreeNode* pRoot){if(pRoot==NULL){return true;}//判断左子树和右子树高度差if(abs(Depth(pRoot->left)-Depth(pRoot->right))>1){return false;}//同时判断右子树和左子树是不是都满足这个条件returnIsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);}};

二叉树的下一个结点

题目来源：牛客网

1、问题描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

2、思路解析

中序遍历对于不同节点来说下一个节点位置也是不同的，左子节点的下一个节点就是父节点，父节点的下一个节点就是右子节点，左子树的最右边的节点的下一个节点就是根节点，根节点的下一个结点就是右子树的最左节点，要是分情况求下一个节点这就很复杂，最简单的方式就是将节点插入到数组中，然后求当前节点的下一个节点就行。要存储节点到数组就得求树的根节点，所以root->next一直NULL
就会求到树的根节点。

3、代码实现

class Solution {
public:intDepth(TreeNode*root){if(root==NULL){return0;}returnmax(Depth(root->left)+1,Depth(root->right)+1);}
    bool IsBalanced_Solution(TreeNode* pRoot){if(pRoot==NULL){return true;}//判断左子树和右子树高度差if(abs(Depth(pRoot->left)-Depth(pRoot->right))>1){return false;}//同时判断右子树和左子树是不是都满足这个条件returnIsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);}};

对称的二叉树

题目来源：牛客网

1、问题描述

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

2、思路解析

思路:递归
先判断根节点是不是为NULL，为NULL也使对称二叉树。对称二叉树就是判断左右子树是不是互为镜像，所以将左子树和右子树交给递归函数判断是不是互为镜像二叉树。当两个节点为NULL时就证明当前路径已经走完了，向上一层返回true，当其中一个节点为NULL时就返回false，还有当两个节点的值不相等时也返回false，接着递归同时判断左子节点的子树右子节点的右子树是不是互为镜像。

3、代码实现

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/classSolution{public:bool_isSymmetrical(TreeNode *root1,TreeNode*root2){if(root1==NULL&&root2==NULL){returntrue;}elseif(root1==NULL||root2==NULL){returnfalse;}if(root1->val!=root2->val){returnfalse;}return_isSymmetrical(root1->left, root2->right)&&_isSymmetrical(root1->right, root2->left);}boolisSymmetrical(TreeNode* root){//判断左子树和右子树是不是存在镜像if(root==NULL){returntrue;}return_isSymmetrical(root->left,root->right);}};

序列化二叉树

题目来源：牛客网

1、问题描述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

2、思路解析

序列化：采用与层序遍历相似的做法，用’!‘标示数值的结束，用’#‘标示空节点，序列化的过程很简单，用队列完成层序遍历，先将根节点入队，然后每次出队一个元素就尝试将其左右儿子加入队列，若无就在字符串后加上’#‘，否则加上"val" + "!"即可
反序列化：反序列化就是一个层序遍历的逆过程，我们先对序列化的字符串做一下预处理，根据’!'对每个结点进行分割，用一个vector来存储每个结点所对应的字符串，然后就可以开始层序遍历了。首先将根节点入队，然后每次尝试从vector中取出来个节点，若不为空，则创建节点后入队，以此类推知道遍历完字符串即完成反序列化
中间采用C++的string，最后转换为C风格字符串即可

3、代码实现

class Solution {
public:char*Serialize(TreeNode *root){    
        string ret;if(!root)return nullptr;
        queue<TreeNode*> q;
        q.emplace(root);// 根结点入队
        ret +=to_string(root->val)+'!';// 记录节点值while(q.size()){
            TreeNode* p = q.front(); q.pop();// 队头出队if(p->left){// 若不为空，加上"val" + "!"
                ret +=to_string(p->left->val)+'!';
                q.emplace(p->left);}else ret +='#';// 为空这加上'#'if(p->right){
                ret +=to_string(p->right->val)+'!';
                q.emplace(p->right);}else ret +='#';}char* ans = new char[ret.size()+1];strcpy(ans, ret.c_str());return ans;}

    TreeNode*Deserialize(char*str){if(!str)return nullptr;
        string data =string(str);
        vector<string> vec;// 先对data预处理一下for(int i =0; i < data.size(); i++){if(data[i]=='#') vec.push_back(string("#"));// 为空则用"#"表示else{int j = i;while(data[j]!='!')++j;
                vec.push_back(data.substr(i, j - i));// 不为空则用"val"表示
                i = j;}}// stoi()函数可以将string转换为int
        TreeNode* root = new TreeNode(stoi(vec[0]));// 创建根节点
        queue<TreeNode*> q;
        q.emplace(root);// 根节点入队int k =1;while(k < vec.size()){
            TreeNode* p = q.front(); q.pop();
            TreeNode *l = nullptr,*r = nullptr;if(vec[k]!="#"){// 若左儿子非空
                l = new TreeNode(stoi(vec[k]));
                q.emplace(l);}
            p->left = l;if(vec[k +1]!="#"){// 若右儿子非空
                r = new TreeNode(stoi(vec[k +1]));
                q.emplace(r);}
            p->right = r;
            k +=2;// 指针向后后移动两步}return root;}};

二叉树中和为某一值的路径(三)

题目来源：牛客网

1、问题描述

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

2、思路解析

思路：双递归
因为路径不是从根节点开始的，也不知道从哪个结点开始，所以就让每个节点都当作开始节点递归寻找路径，所以这是一次递归，还有以每个节点为开始节点有一个递归寻找路径DFS寻找路径这有一次递归。
1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
4：剩余的sum等于当前节点值则找到一种情况。

3、代码实现

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {int count=0;
public:/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */void_FindPath(TreeNode* root,int sum){if(root==NULL){return;}if(sum-root->val==0){
            count++;}_FindPath(root->left, sum-root->val);_FindPath(root->right,sum-root->val);}intFindPath(TreeNode* root,int sum){// write code hereif(root==NULL){return0;}_FindPath(root,sum);FindPath(root->left, sum);FindPath(root->right, sum);return count;}};