用递归解决树问题
- 关于递归的一些理论和思考
- 自顶向下
- 自底向上
- 总结
- 二叉树的最大深度
- 对称二叉树
- 递归写法
- 迭代写法
- 路径总和
- 递归写法
关于递归的一些理论和思考
运用递归解决树的问题
“自顶向下”的解决方案
“自底向上”的解决方案
递归是解决树的相关问题最有效和最常用的方法之一。
接下来以这样一个问题：给定一个二叉树，请寻找它的最大深度。进行举例学习
自顶向下
“自顶向下” 意味着在每个递归层级，我们将首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。 所以 “自顶向下” 的解决方案可以被认为是一种前序遍历。
根结点的深度为1，对于一个结点，如果此结点的深度为k，则子结点深度为k+1。在不断自顶向下往深度遍历时，更新最大深度值（即为树的深度）
int answer=0;//需要一个全局遍历（或不受递归函数内部影响的变量）
void finddepth(TreeNode* root,int depth){
if(root==NULL)
return ;//结束
//该条件其实也可无，这样只是减少max的判断次数，只有当为叶子结点时才判断
if(!root->left&&root->right)
answer=max(answer,depth);//更新最大值，max需要
finddepth(root->left,depth+1);
finddepth(root->right,depth+1);
}
finddepth(root,1);//called in main
自顶往深处，利用子结点为根节点深度+1来进行关键参数的传递，利用一个递归函数无关变量来记录最终深度。
结果在递归中被更新
自底向上
在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历的一种。
根结点的深度=max(左子树的深度，右子树的深度)+1
相比之前自顶向下的思考：子结点的深度=根结点深度+1，最大的深度即为depth
int finddepth(TreeNode* root,int depth){
if(root==NULL)
return 0;//结束
int left=finddepth(root->left,depth);
int right=finddepth(root->right,depth);
return max(left,right)+1;//上一层（根结点）与这一层（子树）关系
}
finddepth(root,0);//called in main
结果在递归中被传递
总结
了解递归并利用递归解决问题并不容易。
当遇到树问题时，请先思考一下两个问题：
- 你能确定一些参数，从该节点自身解决出发寻找答案吗？
- 你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？
如果答案都是肯定的，那么请尝试使用 “自顶向下” 的递归来解决此问题。
或者你可以这样思考：对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？ 如果答案是肯定的，那么 “自底向上” 的递归可能是一个不错的解决方法。
接下来是题目
二叉树的最大深度
不同于上面例子代码
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==NULL)
return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
当然也可自己再嵌套一个函数，函数内部为上面例子那样
复杂度分析：
时间复杂度：O(n)
空间复杂度：最差O(n)，平均情况O(logn)
对称二叉树
递归写法
如果一颗树的左右子树互相镜像，为对称。
即两颗子树的结点值相同，并且树的右结点和另一颗树左结点镜像对称
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL)
return true;
return isM(root->left, root->right);
}
bool isM(TreeNode* l, TreeNode* r) {
if (l == NULL && r == NULL)
return true;
if (l == NULL || r == NULL)
return false;
if (l.val != r.val)
return false;
return isM(l->left, r->right) && isM(l->right, r->left);
}
};
迭代写法
使用两个队列来分别记录左右子树的结点情况，但是对于左子树的结点：先left-child 再right-child；而右子树的结点顺序相反，比较出栈的情况
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL)
return true;
queue A;
queue B;
//就算是NULL也先进队，因为会由NULL和结点比较出不镜像
A.push(root->left);
B.push(root->right);
bool answer = true;
while (1) {
TreeNode* AP = A.front();
A.pop();
TreeNode* BP = B.front();
B.pop();
if (AP == NULL && BP == NULL) {
answer = true;
if (A.empty() && B.empty())
break;
continue;//不继续下面判断，由队列出队
}
if (AP == NULL || BP == NULL) {
answer = false;
break;
}
if (AP->val != BP->val) {
answer = false;
break;
}
//顺序不同
A.push(AP->left);
A.push(AP->right);
B.push(BP->right);
B.push(BP->left);
}
return answer;
}
};
路径总和
递归写法
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (!root)
return false;
sum -= root->val;//自顶向下，减去根的值，到叶子结点判断是否为0
if (!root->left && !root->right)
return (sum == 0);
return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}
};