Day18 2023.1.31 搜索与回溯算法（中等）

剑指offer 55 - Ⅰ. 二叉树的深度

自己实现

这个题就是纯纯简单的DFS，当然用BFS也可以做，这里使用的是DFS

代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int max;
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        max=0;
        recur(root,0);
        return max;
    }
    void recur(TreeNode* root, int depth){
        if(root==NULL)return;
        depth++;
        if(depth>max)max=depth;
        recur(root->left,depth);
        recur(root->right,depth);
    }
};

代码表现

剑指offer 55 - Ⅱ. 平衡二叉树

自己实现

自己实现的时候其实受到了上一道题的干扰，去表示出了每个点的深度，但这个地方因为要比较的是左右子树的深度，所以绝对定义的深度在这个地方其实起不了作用。看了题解

题解

采用了剪枝的处理方法，即在递归中要分别对左右子树进行递归，剪枝的策略就在于当左子树已经不符合条件时，就返回-1，并在左子树递归之后、右子树递归之前进行左子树的返回值判断，如果是-1那就直接一直返回-1，这样就不用再浪费时间执行右子树递归了。

同时，这个地方的深度其实是从底部往上算的，即叶子节点深度为1

参考题解后自己编写代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==NULL)return true;
        return recur(root)!=-1;
    }
    int recur(TreeNode* root){
        if(root==NULL)return 0;
        int dep_l = recur(root->left);
        if(dep_l==-1)return -1;
        int dep_r = recur(root->right);
        if(dep_r==-1)return -1;
        return abs(dep_l-dep_r)>1 ? -1 : (dep_l>dep_r?dep_l:dep_r)+1;
    }
};

代码表现

hint：

• 如果涉及到左右子树的深度比较，就要学会将深度从树的底部往上递增，然后采用上面提到的剪枝方法来节省递归时间