剑指Offer（数据结构与算法面试题精讲）C++版——day16

题目一：序列化和反序列化二叉树

    题目：如图8.3所示，请设计一个算法将二叉树序列化成一个字符串，并能将该字符串反序列化出原来二叉树的算法。
    这里考查的其实是二叉树的创建和输出，只需要固定使用前序、中序或者后序遍历即可，比如构建二叉树的时候使用前序遍历，在进行反序列化的时候同样使用前序遍历的方式输出。由于这里需要反序列化为字符串，使用#标识空节点，因此二叉树的数据类型使用char类型。考虑到需要使用参数的形式去序列化构建一颗二叉树，这里使用输入的流的形式不太方便，分析发现可以使用一个队列结构，将需要字符串读入到队列中，然后采用引用类型调用这个存储了字符的队列来构建二叉树，这样就能够实现字符串序列化成一颗二叉树，最终可以得到如下代码：

treeNode* createTree(queue<char>& qu) {char val=qu.front();qu.pop();if(val=='#') {return nullptr;} else {treeNode* node=new treeNode(val);node->left=createTree(qu);node->right=createTree(qu);return node;}
}
treeNode* deserialize(string data) {queue<char> qu;for(int i=0,size=data.length(); i<size; ++i) {qu.push(data[i]);}return createTree(qu);
}
void serialize(treeNode* tree) {treeNode * p=tree;if(p==nullptr) {cout<<"#";return;} else {cout<<p->val;serialize(p->left);serialize(p->right);}
}

题目二：从根节点到叶节点的路径数字之和

    题目：在一棵二叉树中所有节点都在0～9的范围之内，从根节点到叶节点的路径表示一个数字。求二叉树中所有路径表示的数字之和。例如，图8.4的二叉树有3条从根节点到叶节点的路径，它们分别表示数字395、391和302，这3个数字之和是1088。

    由于需要统计从根节点到叶子节点路径数字和，那么需要拿到所有根节点到叶子节点的路径。我们还能够发现，这里可以考虑使用递归来简化代码逻辑，以395这条路径为例，拿到3节点之后，相当于需要得到以9节点和0节点为根节点到叶子节点的和，这里存在一种数值关系，原根节点到叶子节点的和=上一级*10+下一级节点（新根节点）的路径和。
    接下来，分析如何拿到根节点到叶子节点的所有路径，从根节点向下一级节点探索，每次都需要探索左子节点和右子节点，这里立刻会想到前序遍历，当前序遍历拿到最后一个节点，即叶子节点，那么说明路径完整了，这时候终止前面提到的上一级*10+下一级节点（新根节点）的路径和这一遍历过程。于是得到如下代码：

int dfs(treeNode* tree,int path) {if(tree==nullptr) {return 0;}path=path*10+tree->val;if(!tree->left&&!tree->right) {return path;}return dfs(tree->left,path)+dfs(tree->right,path);
}int getAllPathSum(treeNode* tree) {return dfs(tree,0);
}

    这里的代码将递推关系和前序遍历巧妙的结合起来，这里再回过头捋一下思路，由于发现可以使用递归的形式计算下层根节点到叶子节点的值，因此可以整体上使用dfs(tree->left)+dfs(tree->right)的形式实现，递归的出口有两个：
（1）一开始树就为空，或者子树左右两边中一边为空；
（2）递归扫描到了叶子节点；
    为了保证每次path值都能带入之后的计算，所以使用参数dfs传参的方式向后传递，这里巧妙的是利用dfs(tree,0)开启扫描，让入口和接下来的遍历递推关系统一起来。

题目三：向下的路径节点值之和

    题目：给定一棵二叉树和一个值sum，求二叉树中节点值之和等于sum的路径的数目。路径的定义为二叉树中顺着指向子节点的指针向下移动所经过的节点，但不一定从根节点开始，也不一定到叶节点结束。例如，在如图8.5所示中的二叉树中有两条路径的节点值之和等于8，其中，第1条路径从节点5开始经过节点2到达节点1，第2条路径从节点2开始到节点6。

    结合上一题的思路，这里同样是需要使用先根节点、然后左孩子、右孩子的先序深度遍历，区别在于这里的path值计算不一致，前面是用位数统计，这里只需要统计和。由于题意中描述说这里不仅仅需要考虑到跟到叶子节点的可能路径数，还需要考虑到中间节点到其余节点的可能值，因此既需要考虑携带path向后递归，又需要考虑不携带path从新节点触发的可能路径数。还有一种情况需要考虑，在图的深度优先遍历时，我们常常需要考虑剪枝，这里由于没有说明每个节点的数值是多少（没有说每个节点的数值都是正数），因此不能提前找到路径就终止递归。于是得到如下代码：

void dfs(treeNode* tree,int path,int sum,int& count) {if(tree==nullptr) {return;}path=path+tree->val;if(path==sum) {count++;}if(!tree->left&&!tree->right) {return;}dfs(tree->left,path,sum,count);//携带传值dfs(tree->right,path,sum,count);dfs(tree->left,0,sum,count);//不携带传值dfs(tree->right,0,sum,count);
}

    这里可以得到一下总结，在使用递归的时候，需要明确如下几点：
（1）递归入口以及进入递归的方式；
（2）递归出口；
（3）递归的递推方式；
    对于统计可以视情况使用引用类型参数，比如这里巧妙的利用count引用类型实现统计所有路径。

附录：源码gitee仓库

    考虑到有些算法需要模拟数据，如果全部放进来代码显得过长，不利于聚焦在算法的核心思路上。于是把所有的代码整理到了开源仓库上，如果想要看详细模拟数据，可在开源仓库自取：【凌空暗羽/剑指Offer-C++版手写代码】。

    我是【Jerry说前后端】，本系列精心挑选的算法题目均基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
    无论是即将踏入职场的应届毕业生，还是想要进一步提升自身技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！