树的遍历和迭代的一些总结
一直在写effective stl的总结,今天换个主题,我们来看看算法,刷leetcode看到了树的遍历的问题和一些迭代的问题,顺便过来总结一番.
-
首先我们来看看mergeTree,是leetcode上面的merge two binary trees:
image.png
题目如上图所示,我们下面来分析一下我们的思路,首先肯定是需要理解题目要干什么,题目的意思就是让我们把两个树"加"起来,类似于去两个树的并集.
接下来,我们肯定要想到迭代啊,因为这种问题都是由一个小的部分可以放大到一个大的部分,针对这个题就是说我们如果我们融合了这两颗的子树,那么我们只需要将根节点相加就完成了,所以以递归的思想来看就是,我们不断的对根节点的子节点调用mergeTrees,这样最终会让所有子树都完成相"加",这样一层一层拓展就完成了整个树的相"加".
然后就是要考虑迭代函数结束的时候了,因为迭代从大的树的根节点到越来越小的树的根节点,最终肯定要结束的,不然迭代就结束不了了.对于我们来说,这个迭代函数的结束情况很简单,如果两个节点有任意一个为空,那么迭代就结束,直接返回另外一个节点即可(这时我们不用考虑另外一个节点是否为空,原因很简单).
这个时候,我们程序的框架就完成了.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (!t1) return t2;
if (!t2) return t1;
TreeNode* node = new TreeNode(t1->val + t2->val);
node->left = mergeTrees(t1->left, t2->left);
node->right = mergeTrees(t1->right, t2->right);
return node;
}
};
理解起来应该并不让人觉得困难,主要是我们要弄清楚迭代的思路.
-
接下来说的也是一个迭代的例子,题目也是leetcode上的flatten-binary-tree-to-linked-list:
image.png
这个题目乍一看不算简单,需要我们的思考才能解决问题,这个问题依然是用递归来解决的,原因还是和上面一样.不过这次的迭代函数需要我们来深思一下了,因为递归没有那么容易了.
首先,我们考虑下迭代函数是在做什么.对于一个最简单的树,如果我们调用迭代函数,要想将树"flatten",那么我们先要将根节点的右节点连到左节点的右子节点上,然后在将左子树连到根节点的右子节点上.
我画了个图,大家看看:
379895094.jpg
手动画图,有点粗糙,不过画了图我们要做的事情就变得明朗起来.
迭代函数的参数是root节点,要做的就是将树"flatten",返回值的话可以是void也可以是root节点,如果是void的话,我们就要加入一个额外的变量来储存节点.我们这里假设返回值是void吧(因为leetcode上给的解题模板就是函数返回值为空,其实返回一个指针也OK),加入一个额外的TreeNode指针prev.迭代函数内部要完成我在图中画的三步,第一步之前,先令prev为右子节点的指针(也就是指向3的TreeNode指针).第一步到第二步的过程中,让左子节点的right等于prev,再让root的右子节点为空(root->right=NULL),用prev来保存左子节点指针(也就是指向2的TreeNode指针).第二步到第三步的过程,我们令root的右子节点为prev(也就是指向2的TreeNode指针),然后再令左子节点为空,最后令prev为root节点就OK了.
这个时候,规律已经很明显了,代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if(root == NULL)
return;
flatten(root->right);
flatten(root->left);
root->right=prev;
root->left = NULL;
prev = root;
}
private:
TreeNode *prev = NULL;
};
- 我们稍稍总结一下迭代这一部分,迭代的问题都是有规律的,也就是说对于一个大的问题,它的解法实际上是和小的问题是类似的,譬如我们上面的树的例子,都是对根节点进行操作,然后呢,对左右子节点调用同样的函数(因为子节点仍然还是树,函数依然是正确的),当节点已经没有子节点时,迭代就结束了,然后迭代会不断返回,最终一颗大树的问题也解决了.
