二叉树与递归

最近经常做到关于二叉树的Easy题。

二叉树的遍历总是和递归绑在一起。

如下题寻找二叉树的最大深度。

原题

思路

用递推的思路来想，从某一个节点出发，它的最大深度就是max(左子节点最大深度，右子节点最大深度) + 1。
对于每一个节点来说都是这样的，那么就可以用递归的办法来解决了。(长度也短)，所以主要是思路问题。

代码

class Solution
{
public:
    int maxDepth(TreeNode *root)
    {
        if (!root)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

类似题目

原题链接

思路

既然是要求高度，那么肯定要用上刚刚的求二叉树深度的函数。比较一下左右节点最大深度绝对值<=1就行了。。。。吗？

注意看题，要求保证每个节点左右两子树高度差绝对值都不超过1。

所以直接比较左右节点只能保证根节点左右子树是平衡的。

既然直接这样写就能判断根节点了，那么是不是也可拓展到任一节点呢。

使用递归的方法就可以实现。

代码

class Solution
{
public:
    bool isBalanced(TreeNode *root)
    {
        if (!root)
            return true;
        return abs(dfs(root->left) - dfs(root->right)) <= 1 &&    //判断当前节点左右子树是否平衡
        isBalanced(root->left) && isBalanced(root->right);        //递归继续判断左右子节点是否平衡
    }
    int dfs(TreeNode *root)         //求当前节点向下的高度
    {
        if (!root)
            return 0;
        return max(dfs(root->left), dfs(root->right)) + 1;
    }
};

小结

递归刚学的时候（当时还在读初一）感觉有点抽象，挺难理解。

实际用起来之后发现确实挺抽象的，感觉应该这样写，然后就能正常跑起来了。

只要设置了个边界条件，它自己就可以走下去。

不过呢，缺点就是数据量大了可能会爆栈，而且不好修改递归函数里的代码，改一发动全身。

一步想错就会导致边界条件设计有问题，直接死循环。

要改的地方越来越多的时候就要回过头好好想想，递归真是这么写的吗？是不是有更好的关系来简洁地解决问题。

不过当写完后运行发现奇迹跑起来了的时候，成就感还是可以的。