Leetcode 二叉树番外篇 —— 搞定所有二叉树递归问题

前言

不知道你有没有刷到过力扣那些二叉树简单题，看解析简简单单三四行代码，但是这样的题多了后，就被绕的摸不着头脑，本篇就打算将这类型的题全部总结一遍，全部都用递归的思路解决。

解题思路

对于这类型的题来说，大都是bool类型判断。一般分两类：

• 不需要构造辅助函数
  • 单树问题：题目只给了你一棵树
  • 双树问题：题目给了你两棵树，这一类型的题也是最多的
• 需要构造辅助函数
  这类型的题目只用根节点子树对称无法完全解决问题，必须要用到子树的某一部分进行递归，即需要调用辅助函数比较两个子树。

解题模板

对于单树而言，首先要有递归结束条件，一般都是特殊的判断，比如判断是否为空。比如：

if(!root) return true/false;
if(!root->left) return true/false/递归函数;
if(!root->right) return true/false/递归函数;
1
2
3

对于双树问题，也是如此：

if(!root) return true/false;
if(!root->left) return true/false/递归函数;
if(!root->right) return true/false/递归函数;
1
2
3

下面就根据具体的题来具体分析。

100. 相同的树

100. 相同的树

1. 特殊判断：当两棵树都为空，则必然相同
2. 如果两棵树其中一个为空，则false
3. 递归：根节点值相同 + 左子树相同 + 右子树相同

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q)
            return true;
        if(!p || !q)
            return false;
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
1
2
3
4
5
6
7
8
9
10

104. 二叉树的最大深度

104. 二叉树的最大深度

1. 特殊判断：如果树为空，则最大深度为0
2. 获取左右子树最大深度+1

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return max(maxDepth(root->left)+1, maxDepth(root->right)+1);
    }
};
1
2
3
4
5
6
7
8

110. 平衡二叉树

110. 平衡二叉树

根节点左右子树高度差 <= 1 + 左子树是平衡二叉树 + 右子树是平衡二叉树

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root)
            return true;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        if(abs(left-right) > 1)
            return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        return max(maxDepth(root->left)+1, maxDepth(root->right)+1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

965. 单值二叉树

965. 单值二叉树

1. 如果节点为空，则为true
2. 判断当前节点分别和左右节点是否相同，如果不同则false
3. 左子树是单值二叉树 + 右子树是单值二叉树

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if(!root)
            return true;
        int val = root->val;
        if(root->left && root->left->val != val)
            return false;
        if(root->right && root->right->val != val)
            return false;
        return isUnivalTree(root->left) && isUnivalTree(root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

226. 翻转二叉树

226. 翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
            return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11

617. 合并二叉树

617. 合并二叉树

1. 若有一个为空，则返回另一个
2. 把两棵树根节点值相加
3. 递归合并左右子树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1)
            return root2;
        if(!root2)
            return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

101. 对称二叉树

101. 对称二叉树

这题需要构造辅助函数。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
    bool check(TreeNode* left, TreeNode* right) {
        if(!left && !right)
            return true;
        if(!left || !right)
            return false;
        return left->val == right->val && check(left->left, right->right) && check(left->right, right->left);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

572. 另一棵树的子树

572. 另一棵树的子树

1. 有一颗树为空就不成立
2. 判断两棵树是否相同（100题）
3. 判断左子树和该树是否相同 || 判断右子树和该树是否相同

class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(!root || !subRoot)
            return false;
        if(isSameTree(root, subRoot))
            return true;
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
    bool isSameTree(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2)
            return true;
        if(!root1 || !root2)
            return false;
        return root1->val == root2->val && isSameTree(root1->left, root2->left) && isSameTree(root1->right, root2->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LCR 143. 子结构判断

LCR 143. 子结构判断

注意区分这个题和572的区别，这个只需要部分满足就可以了，不需要两棵树完全相同。

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B)
            return false;
        if(isSubtree(A, B))
            return true;
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
    bool isSubtree(TreeNode* a, TreeNode* b) {
        if(!b)
            return true;
        if(!a || a->val != b->val)
            return false;
        return isSubtree(a->left, b->left) && isSubtree(a->right, b->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17