代码随想录刷题Day36

这道题，受对称树、相同树的题目启发，可以在遍历树的同时，尝试比较树的不同节点作为根节点的树，是否和给出的子树结构和值均相同。

class Solution {
public:bool isSame(TreeNode* p,TreeNode* q){//自身节点的比较if(p==nullptr && q==nullptr) return true;else if(p==nullptr && q!= nullptr) return false;else if(p!=nullptr && q==nullptr) return false;else if(p->val != q->val) return false;//左右两侧节点的比较bool left_bool = isSame(p->left,q->left);bool right_bool = isSame(p->right,q->right);return left_bool && right_bool;}bool isSubtree(TreeNode* root, TreeNode* subRoot) {//层序遍历树的节点，如果节点的值和subRoot的值相同，则比较，如果同，则返回true;queue<TreeNode*> levelQueue;levelQueue.push(root);TreeNode* tmp;int cnt = 1;while(!levelQueue.empty()){cnt = levelQueue.size();while(cnt--){tmp = levelQueue.front();levelQueue.pop();if(tmp!=nullptr && tmp->val ==subRoot->val && isSame(tmp,subRoot)){return true;}if(tmp->left) levelQueue.push(tmp->left);if(tmp->right) levelQueue.push(tmp->right);}}return false;}
};

这道题之前用过层序遍历的方法，逐层记录层高，这次想要换一种思路，但自己直接很难想出来，比较难想到的是如何去定义递归函数的作用。看了代码随想录的相关视频后才明白了。原来这可以做一个从叶子节点到根节点逐层高度加一，类似后序遍历的方式去迭代获得树的高度。

int maxDepth(TreeNode* root) {//从树的最下方往最上方依次层高+1if(root==nullptr) return 0;else{return (max(maxDepth(root->left),maxDepth(root->right))+1);}}
};

这道题以此类推，从孩子节点层往根节点的过程，高度递增：

class Solution {
public:int maxDepth(Node* root) {if(root==nullptr) return 0;else{int max_height = 0;//记录孩子节点中最高的那个节点的高度for(int i = 0;i<(root->children).size();i++){max_height = max(max_height,maxDepth((root->children)[i]));}//当前节点高度要比孩子节点高度多1return max_height+1;}}
};

之前层序遍历系列中做个这样的题目，这里尝试使用递归的方式来求解这个题目。但是如果是想要仿照上面的思路来解答的话，并不是简单把max改为min，因为那样的话，最小深度的那条计算路径可能不包含叶子节点（如下值为8的节点，最小深度不是右孩子深度0+1，而是2）。

所以对于求树的最小深度的递归层，需要对节点的最小深度有明确的定义：

• 节点为空，则最小深度为0
• 节点是叶子节点（既没有左孩子，也没有右孩子），则深度为1
• 节点只有一个孩子，则深度是孩子深度+1（则是和最大深度最大的区别，）
• 节点有两个孩子，则是深度更小的孩子的深度+1（同最大深度的算法）
  代码如下：

class Solution {
public:int minDepth(TreeNode* root) {if(!root) return 0;else if(root->left == nullptr && root->right ==nullptr) return 1;else if(root->left ==nullptr && root->right !=nullptr) return minDepth(root->right)+1;else if(root->left != nullptr && root->right ==nullptr) return minDepth(root->left)+1;else{return min(minDepth(root->left),minDepth(root->right))+1;}}
};

总之，还是旧心得，递归题目的重点是要明确递归函数的三要素，尤其是递归函数的功能和递归函数层的实现逻辑。