递归案例_牛客博客

文章目录

24. 两两交换链表中的节点
104. 二叉树的最大深度
110. 平衡二叉树
101. 对称二叉树
226. 翻转二叉树
617. 合并二叉树
83. 删除排序链表中的重复元素
验证二叉搜索树
100. 相同的树

24. 两两交换链表中的节点

给定 1->2->3->4, 你应该返回 2->1->4->3.

递归解法

主要就是递归的三部曲：

找终止条件：本题终止条件很明显，当递归到链表为空或者链表只剩一个元素的时候，没得交换了，自然就终止了。
返回值：返回给上一层递归的值应该是已经交换完成后的子链表.
单次的过程：因为递归是重复做一样的事情，所以从宏观上考虑，只用考虑某一步是怎么完成的。我们假设待交换的俩节点分别为head和next，next的应该接受上一级返回的子链表(参考第2步)。就相当于是一个含三个节点的链表交换前两个节点，就很简单了，想不明白的画画图就ok。

ListNode* swapPairs(ListNode* head) {
	// 终止条件
    if(head==nullptr || head->next==nullptr) return head;
    ListNode* tmp = head->next;
    // 返回已转换完成的子链表，head->next->next = 交换完的子链表
    // 1->2->3->4->5 --- 1(head)->2(next) 4->3->5(交换完成的子链表)
    head->next = swapPairs(tmp->next);
    tmp->next = head;   
    return tmp;
}

/* ListNode* swapPairs(ListNode* head) { if(head==nullptr || head->next==nullptr) return head; ListNode* tmp = head->next; head->next = tmp->next; tmp->next = head; swapPairs(head->next); return tmp; } */

104. 二叉树的最大深度

找终止条件：什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。
找返回值。应该返回什么，我们需要返回当前这一层对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。
级递归应该做什么。首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，看下图。此时就三个节点：root、root.left、root.right，其中根据第二步，root.left和root.right分别记录的是root的左右子树的最大深度。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。

int maxDepth(TreeNode* root) {
        if(!root) return 0; 
        int lde = maxDepth(root->left);
        int rde = maxDepth(root->right);
        return max(lde,rde)+1;
    }

110. 平衡二叉树

找终止条件：当子树为空时，深度为0,自然为平衡树；
找返回值：每一层递归，我们都有三个节点，root、left、right，而对于一颗树，它是一个平衡二叉树需要满足三个条件：它的左子树是平衡二叉树，它的右子树是平衡二叉树，它的左右子树的高度差不大于1。换句话说：如果它的左子树或右子树不是平衡二叉树，或者它的左右子树高度差大于1，那么它就不是平衡二叉树。

而在我们眼里，这颗二叉树就3个节点：root、left、right。那么我们应该返回什么呢？如果返回一个当前树是否是平衡二叉树的boolean类型的值，那么我只知道left和right这两棵树是否是平衡二叉树，无法得出left和right的高度差是否不大于1，自然也就无法得出root这棵树是否是平衡二叉树了。而如果我返回的是一个平衡二叉树的高度的int类型的值，那么我就只知道两棵树的高度，但无法知道这两棵树是不是平衡二叉树，自然也就没法判断root这棵树是不是平衡二叉树了。

本次递归应该做什么：知道了第二步的返回值后，这一步就很简单了。目前树有三个节点：root，left，right。我们首先判断left子树和right子树是否是平衡二叉树，如果不是则直接返回false。再判断两树高度差是否不大于1，如果大于1也直接返回false。否则说明以root为节点的子树是平衡二叉树，那么就返回true和它的高度。

参考自

我们直接用左右子树的高度差作为判据标准，如果存在某层递归满足不平衡条件abs(lde-rde)>1，则将标志位置0，剩余节点也不必继续递归，因为已经不满足平衡性。

class Solution {
public:
    bool flag = true;
    int dfs(TreeNode* root){
        if(!root || !flag) return 0;
        int lde = dfs(root->left);
        int rde = dfs(root->right);
        if(abs(lde-rde)>1) flag=false;
        return max(lde,rde)+1;
    }

    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        dfs(root);
        return flag;
    }
};

101. 对称二叉树

递归

递归结束条件：

两个节点都为空
一个为空，另一个非空
都为非空，但是值不相等
都为非空，但是值相等（再次进入递归）

bool dfs(TreeNode* le,TreeNode* ri){
        if(!le && !ri) return true;
        if(!le || !ri) return false;
        if(le->val == ri->val){
            return dfs(le->left,ri->right) && dfs(le->right,ri->left);
        }
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        if(!root->left && !root->right) return true;
        if(!root->left || !root->right) return false;
        return dfs(root->left,root->right);
    }

迭代

// 队列迭代的方法 层次遍历二叉树，判断每层二叉树组成的 数组是否是 回文数组即可

bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        if(!root->left && !root->right) return true;
        if(!root->left || !root->right) return false;
        queue<TreeNode*> mq;
        mq.push(root->left);
        mq.push(root->right);
        int size = 0;
        while(!mq.empty()){
            vector<int> c_vec;
            size = mq.size();
            for(;size!=0;size--){
                TreeNode* cur = mq.front();
                mq.pop();
                // 空节点，数值记录为0，然后跳过
                if(!cur){
                    c_vec.push_back(0);
                    continue;
                }
                mq.push(cur->left);
                mq.push(cur->right);
                c_vec.push_back(cur->val);
            }

            int len = c_vec.size();
            for(int i=0;i<len/2;i++){
                if(c_vec[i] != c_vec[len-i-1]) return false;
            }
        }
        return true;
    }

// bool isSymmetric(TreeNode* root) {
// if(!root) return true;
// if(!root->left && !root->right) return true;
// if(!root->left || !root->right) return false;
// queue<TreeNode*> mq;
// mq.push(root->left);
// mq.push(root->right);
// int size = 0;
// while(!mq.empty()){
// size = mq.size();
// TreeNode* t1 = mq.front();
// mq.pop();
// TreeNode* t2 = mq.front();
// mq.pop();
// if(!t1 && !t2) continue;
// if(!t1 || !t2) return false;
// if(t1->val != t2->val) return false;
// mq.push(t1->left);
// mq.push(t2->right);
// mq.push(t1->right);
// mq.push(t2->left);
// }
// return true;
// }

226. 翻转二叉树

终止条件：当前节点为空，即根节点，不需要翻转，直接返回
返回值: 返回已经翻转好的子树
当级处理过程：存在三个节点，root,left,right，其中left\right是已经翻转好的子树，这时只需翻转当前层次即可root->left = right root->right=left，即完成当前层次的翻转

TreeNode* invertTree(TreeNode* root) {
     if(!root) return root;
     // 交换左右节点，然后再分别递归交换左右节点
     TreeNode* tmp = root->left;
     root->left = root->right;
     root->right = tmp;
     
     invertTree(root->left);
     invertTree(root->right);
     return root;
 }

// 2 另一种，先递归到最底层，然后再开始交换
TreeNode* invertTree(TreeNode* root) {
   if(!root) return root;
    TreeNode* ri = invertTree(root->right);
    TreeNode* le = invertTree(root->left);
    root->left = ri;
    root->right = le;
    return root;
}

617. 合并二叉树

终止条件：其中一个树为空，直接返回，拼接起来即可；
返回值：然后已合并的子树
每级处理过程：更新root的值，使用第二步返回的新子树去更新left 和 right 的指针；

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1 && !t2) return nullptr;
        if(!t1) return t2;
        if(!t2) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left,t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

83. 删除排序链表中的重复元素

终止条件：当链表为空或只有一个元素时，不可能重复，直接返回；
返回值: 返回已经去重的子链表
处理函数：递归后，应该存在两个节点，头结点和处理完成的子节点dfs(head->next),如果当前头结点等于上级返回节点的头结点，则会重复节点，丢弃当前节点(直接返回上级返回的节点)，不相等，则将两个节点拼接，并返回新的子链表节点

class Solution {
public:
   ListNode* dfs(ListNode* head){
       if(!head->next) return head;
       ListNode* tmp = dfs(head->next);
       if(head->val == tmp->val) return tmp;
       else head->next = tmp;
       return head;
   }
   ListNode* deleteDuplicates(ListNode* head) {
       if(!head || !head->next) return head;
       return dfs(head);
   }
};

验证二叉搜索树

注意：不仅右子结点要大于该节点，整个右子树的元素都应该大于该节点。不仅左子结点要小于该节点，整个左子树的元素都应该小于该节点。因此要关注每个节点的上下界。

递归1

终止条件: 当前节点为空节点，则一定满足；
返回值：判断当前节点是否为平衡二叉树,需要三个关系 1.左右子树为平衡二叉树 2.左子树所有元素(最大值) 小于当前节点 3.整个右子树的元素(最小值) 大于当前节点，所以我们不仅需要返回左右子树是否平衡，还需要左右子树的上下界问题
处理函数：判断当前节点的左右子树是否满足平衡且当前节点值满足上下界关系。

class Solution {
public:
    bool dfs(TreeNode* root,long low,long up){
        if(!root) return true;
        if(root->val <= low || root->val >= up) return false;
        //递归左子树，当前节点值为 上界
        bool lr = dfs(root->left,low,root->val);
        // 递归右子树，当前节点值为下界
        bool ri = dfs(root->right,root->val,up);
        return lr&&ri;
    }

    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        return dfs(root,LONG_MIN,LONG_MAX);
    }
};

中序遍历(满足升序数组)

void helper(TreeNode* root,vector<int>& ans){
    if(!root) return ;
    helper(root->left,ans);
    ans.push_back(root->val);
    helper(root->right,ans);
}
bool isValidBST(TreeNode* root) {
    if(!root) return true;
    vector<int> ans;
    helper(root,ans);
    for(int i=0;i<ans.size()-1;i++){
        if(ans[i] >= ans[i+1]) return false;
    }
    return true;
}

100. 相同的树

bool isSameTree(TreeNode* p, TreeNode* q) {
        // 终止条件
        if(!p && !q) return true;
        if(!p || !q) return false;
        // 处理函数
        if(p->val != q->val) return false;
        //返回值
        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }