二叉树专题

Leetcode 104. 二叉树的最大深度

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

Leetcode 100. 相同的树

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(p && q == nullptr || q && p == nullptr)  return false;if(p == nullptr && q == nullptr)            return true;if(p -> val != q -> val)    return false;bool left = isSameTree(p -> left, q -> left);bool right = isSameTree(p -> right, q ->right);return left && right;}
};

Leetcode 572. 另一棵树的子树

方法一：暴力匹配

上一题问题的延伸，主要注意下什么时候用isSubtree什么时候用isSametree就可以。

class Solution {
public:bool isSametree(TreeNode* a, TreeNode* b){if(a == nullptr && b || a && b == nullptr)  return false;if(a == nullptr && b == nullptr)            return true;if(a -> val != b -> val)                    return false;return isSametree(a -> left, b -> left) && isSametree(a -> right, b -> right);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(root && subRoot == nullptr || root == nullptr && subRoot)    return false;if(root -> val != subRoot -> val)return isSubtree(root -> left, subRoot) || isSubtree(root -> right, subRoot);return isSametree(root, subRoot) || isSubtree(root -> left, subRoot) || isSubtree(root -> right, subRoot);}
};

方法二：只在高度相同时匹配

class Solution {
public:int getHeight(TreeNode* root){if(root == nullptr)     return 0;return max(getHeight(root -> left), getHeight(root -> right)) + 1; }bool isSametree(TreeNode* a, TreeNode* b){if(a == nullptr && b || a && b == nullptr)  return false;if(a == nullptr && b == nullptr)            return true;if(a -> val != b -> val)                    return false;return isSametree(a -> left, b -> left) && isSametree(a -> right, b -> right);}bool isSubtree(TreeNode* root, TreeNode* subRoot) { // 只在相同高度才进行比较int hs = getHeight(subRoot);function<pair<int, bool>(TreeNode*)>  dfs = [&](TreeNode* r)->pair<int, bool>{  // 返回pair类型<结点高度,是否与subRoot相同>if (nullptr == r)   return {0, false};    // 高度为0,不是相同子树auto [l_h, l_fg] = dfs(r -> left);auto [r_h, r_fg] = dfs(r -> right);if (l_fg || r_fg)   return {0, true};        // 至少一个存在即可int cur_h = max(l_h, r_h) + 1;return {cur_h, cur_h == hs && isSametree(r, subRoot)};  // 相等的时候再去比较}; return dfs(root).second;}
};