【Hello Algorithm】二叉树的递归套路

本篇博客介绍： 介绍二叉树的递归套路算法

递归思路

我们下面使用的树形DP方法的时间复杂度全部是O（N）的

如果不理解为什么是O（N）的同学可以参考我上一篇博客的递归序

使用下面的方法写代码有两个好处

• 给我们思想提醒
• 代码模板化

思想提醒

不管我们遇到什么题目 我们都会先想以X为头节点的时候会遇到什么情况

而我们实现的手段就是我们可以向左右子树要信息 根据这些信息我们就可以列出可能性

在可能性全部覆盖到的情况下 我们的代码就对了

高度模板化

刷题的时候我们都会按照下面的顺序写代码

• 以X节点为头 可以向左树右树要什么信息
• 在上一步的前提下 以X为头节点得到的答案有什么可能性
• 列出向左右子树索要信息的结构体info
• 实现base case
• 向左右子树要信息 完成所有可能性

判断二叉树是否是平衡二叉树

平衡二叉树的定义为

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

这里需要注意的是每个子树都要满足平衡二叉树的定义最后才满足

下面是我们的思路

我们假设 现在有一个节点X 我们想要知道以X为头的树是否是平衡二叉树 那么我们需要知道什么信息呢？

我们说 只要知道下面三个条件我们能确定X为头的树是平衡二叉树

• x的左子树为平衡二叉树
• x的右子树为平衡二叉树
• x的左子树和右子树高度的差值小于等于1

那么我们现在要做的是 创造一个结构体 info 收集左右子树的信息 再通过后序遍历的方式依次上交给父节点

父节点做出下判断即可

其次我们要判断空节点是否是平衡二叉树（是的）

整体的代码如下

class Solution {
public:
    struct info
    {
        bool isBalanced; 
        int height;

        info(bool i , int h)
        {
            isBalanced = i;
            height = h;
        }
    };

    info* Process(TreeNode* root)
    {
        if (root == nullptr)
        {
            return new info(true , 0);
        }

        info* left = Process(root->left);
        info* right = Process(root->right);

        int height = max(left->height , right->height) + 1;
        bool isBalanced = true;
        if (!left->isBalanced || !right->isBalanced)
        {
            isBalanced = false;
        }

        if (abs(left->height - right->height) > 1)
        {
            isBalanced = false;
        }

        return new info(isBalanced , height);
    } 


    bool isBalanced(TreeNode* root) 
    {
        return Process(root)->isBalanced;
    }
};

判断二叉树是否是搜索二叉树

首先我们要了解下关于搜索二叉树的定义

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数
• 节点的右子树只包含 大于 当前节点的数
• 所有左子树和右子树自身必须也是二叉搜索树

需要注意的是 一般来说 我们的经典搜索二叉树是不支持插入重复数值的节点的

下面是我们的思路

首先我们接下来做的所有题目都是以我们能够向左右子树要到数据作为前提的 这就能够帮助我们理清一些思路 或者说能够引导我们去怎么想

我们应该去要哪些数据？ 对于这道题目来说

• x的左树是否为搜索二叉树
• x的右树是否在搜索二叉树
• x左树的最大值
• x右树的最小值

可以这里我们就有一个问题了 对于x左右树来说 我们要的数据不一样

那么这个时候我们的操作就应该是求全集

这是因为我们的代码是要进递归的 而进了递归之后一个节点可能在左也可能在右 所以说如果我们只拿一个值是不能够满足要求的

此外由于我们无法判断一颗空树的左右节点最大值 所以我们的base case选择返回一个空指针即可 我们在递归程序里面再对空进行处理

class Solution {
public:
    struct info
    {
        bool isBST;
        int max;
        int min;

        info(bool i , int ma , int mi)
        {
            isBST = i;
            max = ma;
            min = mi;
        }
    };

    info* process(TreeNode* root)
    {
        if (root == nullptr)
        {
            return nullptr;
        } 

        info* left = process(root->left);
        info* right = process(root->right);

        int max = root->val;
        int min = root->val;
        bool isBST = true;

        if (left) // != nullptr
        {
            max = std::max(max , left->max);
        }

        if (right)
        {
            max = std::max(max , right->max);
        }

        if (left)
        {
            min = std::min(min , left->min);
        }

        if (right)
        {
            min = std::min(min , right->min);
        }

        if (left && !left->isBST)
        {
            isBST = false;
        }

        if (right && !right->isBST)
        {
            isBST = false;
        }

        if (left && left->max >= root->val)
        {
            isBST = false;
        }

        if (right && right->min <= root->val)
        {
            isBST = false;
        }

        return new info(isBST , max , min);
    }


    bool isValidBST(TreeNode* root) 
    {
        return process(root)->isBST;
    }
};

返回二叉树节点的最大距离

二叉树的最大距离定义如下

二叉树的直径是指树中任意两个节点之间最长路径的长度 这条路径可能经过也可能不经过根节点 root

两节点之间路径的 长度 由它们之间边数表示

下面是我们的思路

• 我们的X节点有可能在最大路径上
• 我们的X节点有可能不在最大路径上

X节点在最大路径上时

那么此时最大路径肯定是 X左树的最大高度+X右树的最大高度+1

当X节点不在最大路径上时候

此时有两种情况

• 最大路径在X的左子树
• 最大路径在X的右子树

此时我们只需要对比下左右子树的最大路径找到最大值就可以

代码表示如下

class Solution {
public:
    struct info
    {
        int _height;
        int _dbt;

        info(int h , int d)
        {
            _height = h;
            _dbt = d;
        }
    };

    info* process(TreeNode* root)
    {
        if (root == nullptr)
        {
            return new info(0 , 0);
        }

        info* left = process(root->left);
        info* right = process(root->right);

        int height = max(left->_height , right->_height) + 1;

        int p1 = left->_dbt;
        int p2 = right->_dbt;
        int p3 = left->_height + right->_height + 1;

        int dbt = max(max(p1 , p2) , p3);

        return new info(height , dbt);
    }


    int diameterOfBinaryTree(TreeNode* root) 
    {
        return process(root)->_dbt - 1;
    }
};

验证一棵树是否是满二叉树

满二叉树的定义如下

满二叉树除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。

下面是我们的思路

满二叉树的特性保证了 它的2的高度次方-1肯定是它的节点个数

所以说我们只需要遍历整颗二叉树得出节点个数 并且得出高度 之后计算验证下即可

寻找最大的BST子树

LC题目连接

这道题目如果按照我们上面提到的递归思路做将会特别简单

我们只需要考虑两种情况即可

1. 最大的BST子树经过X节点
2. 最大的BST子树不经过X节点

如果最大的BST子树经过x节点 则要满足以下条件

• 左子树为bst子树
• 右子树为bst子树
• 以x节点为头的子树为bst子树
• 验证上面一点则需要左右子树的最大和最小值

如果最大的BST子树不经过x节点 则必定为以下条件

• 左子树是bst子树
• 右子树是bst子树

所以说我们一共需要下面的条件

• 是否为搜索二叉树
• 最大值
• 最小值
• 树的大小
• 树的最大bst子树大小

整体代码如下

class Solution {
public:
    // 最大bst经过x节点
    // 1. 比较x节点和左右子树是否符合条件
    // 
    // 最大bst不经过x节点
    // 1. 左子树是
    // 2. 右子树是
    struct info 
    {
        bool _isBST;
        int _max;
        int _min;
        int _maxsize;
        int _bstsize;

        info(bool b , int ma , int mi , int ms , int sz)
        {
            _isBST = b;
            _max = ma;
            _min = mi;
            _maxsize = ms;
            _bstsize = sz;
        }
    };

    info* process(TreeNode* root)
    {
        if(root == nullptr)
        {
            return nullptr;
        }  

        info* left = process(root->left);
        info* right = process(root->right);

        int rootmax = root->val;
        int rootmin = root->val;
        int rootallsize = 1;

        if (left) 
        {
            rootmax = max(rootmax , left->_max);
            rootmin = min(rootmin , left->_min);
            rootallsize += left->_maxsize;
        }

        if (right)
        {
            rootmax = max(rootmax , right->_max);
            rootmin = min(rootmin , right->_min);
            rootallsize += right->_maxsize;
        }

        int p1 = -1;
        if (left)
        {
            p1 = left->_bstsize;
        }

        int p2 = -1;
        if (right)
        {
            p2 = right->_bstsize;
        }

        int p3 = -1; 

        if ((left == nullptr || left->_isBST) && (right == nullptr || right->_isBST))
        {
            if ((left == nullptr || (left->_max < root->val)) && ((right == nullptr) || (right->_min > root->val)) )
            {
                int leftsize = 0;
                int rightsize = 0;
                if (left)
                {
                    leftsize = left->_bstsize;
                }
                if (right)
                {
                    rightsize = right->_bstsize;
                }

                p3 = leftsize + rightsize + 1;
            }
        }

        int bstsize = max(max(p1 , p2) , p3);
        bool isbst = bstsize == rootallsize;
        return new info(isbst , rootmax , rootmin , rootallsize , bstsize);
    }

    int largestBSTSubtree(TreeNode* root) 
    {
        if (root == nullptr)
        {
            return 0;
        }
        return process(root)->_bstsize;
    }
};

判断二叉树是否是完全二叉树

还是根据我们前面的算法 分为两种情况

• 以X节点为头节点的树是完全二叉树
• 以X节点为头节点的树不是完全二叉树

这两个问题其实是对立的 所以说我们只需要讨论 以X节点为头节点树是完全二叉树的几种情况 之后就是非二叉树的情况了

• 左子树为满二叉树 右子树为满二叉树 左子树和右子树高度相同
• 左子树为完全二叉树 右子树为满二叉树且左子树减右子树的高度为1
• 左子树为满二叉树 右子树为满二叉树 且左子树减右子树的高度为1
• 左子树为满二叉树 右子树为完全二叉树 且左子树和右子树高度相同

我们需要的信息有

• 左子树是否为满二叉树
• 右子树是否为满二叉树
• 高度

代码表示如下

class Solution {
public:
    // 完全二叉树经过x节点
    // 四种可能性
    // 不经过x节点
    // 不满足上面四种可能性

    struct info
    {
        bool _isfull;
        bool _iscpt;
        int _height;

        info(bool isf , bool isc , int h)
        {
            _isfull = isf;
            _iscpt = isc;
            _height = h;
        }
    };

    info* process(TreeNode* root)
    {
        if (root == nullptr)
        {
            return new info(true , true , 0);
        }

        info* left = process(root->left);
        info* right = process(root->right);

        bool rootisfull = false;
        if (left->_isfull && right->_isfull && left->_height == right->_height)
        {
            rootisfull = true;
        }

        int rootheight = max(left->_height , right->_height) + 1;

        bool rootiscpt = false;
        if (rootisfull)
        {
            rootiscpt = true;
        }

        if (left->_iscpt && right->_isfull && (left->_height - right->_height) == 1)
        {
            rootiscpt = true;
        }

        if (left->_isfull && right->_isfull && (left->_height - right->_height) == 1)
        {
            rootiscpt = true;
        }

        if (left->_isfull && right->_iscpt && (left->_height == right->_height))
        {
            rootiscpt = true;
        }

        return new info(rootisfull , rootiscpt , rootheight);
    }


    bool isCompleteTree(TreeNode* root) 
    {
        return process(root)->_iscpt;
    }
};

判断二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）

还是根据我们一开始的套路 这个公共祖先可能根x有关 也可能和x无关

• 如果跟x有关 则说明x就是最近的公共祖先
• 如果跟x无关 则说明x不是最近的公共祖先

如果x是最近的公共祖先则说明

• 找到了A
• 找到了B
• 找到最近的公共节点 （x本身）

如果x不是最近的公共祖先则说明

• 没找到A
• 没找到B
• 公共祖先在左子树
• 公共祖先在右子树

综上 我们需要的信息有

• 节点a有没有被发现
• 节点b有没有被发现
• 公共祖先有没有被发现

代码表示如下

class Solution {
public:
    struct info
    {
        bool Finda;
        bool Findb;
        TreeNode* ans;

        info(bool a, bool b,TreeNode* an)
        {
            Finda = a;
            Findb = b;
            ans = an;    
        }
    };

    info* procrss(TreeNode* root , TreeNode*& p , TreeNode*& q)
    {
        if (root == nullptr)
        {
            return new info(false , false, nullptr);
        }

        info* left = procrss(root->left , p , q);
        info* right = procrss(root->right , p , q);

        bool rootfinda = false;
        bool rootfindb = false;

        if (left->Finda || right->Finda || root == p)
        {
            rootfinda =true;
        }

        if (right->Findb || left->Findb || root == q)
        {
            rootfindb = true;
        }

        TreeNode* rootans = nullptr;
        if (left->ans)
        {
            rootans = left->ans;
        }

        if (right->ans)
        {
            rootans = right->ans;
        }

        if (rootfinda && rootfindb && left->ans == nullptr && right->ans == nullptr)
        {
            rootans = root;
        }

        return new info(rootfinda , rootfindb , rootans);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        return procrss(root , p , q)->ans;
    }
};

打家劫舍三

这是lc上的一道题目 题目连接为

打家劫舍三

具体的题目如下

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

这也是一道典型的树形dp题目

还是一样 根据我们的思路来做 有两种可能性

• 经过X节点
• 不经过X节点

如果说要打劫X节点 那么就不能够打劫X的子节点

如果说不打劫X节点 那么就可以打劫X的子节点 也可以不打劫

根据上面的分析 我们需要两个信息

• 抢劫本节点的最大值
• 不抢劫本节点的最大值

之后根据上面的可能性列代码就可以

整体代码表示如下

class Solution {
public:
    struct info
    {
        int _yes;
        int _no;

        info(int y , int n)
        {
            _yes = y;
            _no = n;
        }
    };

    info* process(TreeNode* root)
    {
        if (root == nullptr)
        {
            return new info(0 , 0);
        }

        info* left = process(root->left);
        info* right = process(root->right);

        int rootyes = 0;
        int rootno = 0;

        rootyes = left->_no + right->_no + root->val;
        rootno = max(left->_no ,left->_yes) + max(right->_no , right->_yes);

        return new info(rootyes , rootno);
    }

    int rob(TreeNode* root) 
    {
        info* info1 = process(root);
        return max(info1->_yes , info1->_no);
    }
};