继续二叉树，直接从 leetcode 开始

104.二叉树的最大深度

要求二叉树的最大深度，第一时间就想到了上一节的层序遍历，在用 DFS 写的时候我们记下了每一层对应的内容，根据这个思路， 返回 DFS 的最大层数即可。

class Solution {
public:
    int ans=0;
    void dfs(TreeNode* root,int depth){
        if(!root) return ;
        ans=max(ans,depth);
        dfs(root->left,depth+1);
        dfs(root->right,depth+1);

    }
    int maxDepth(TreeNode* root) {
        dfs(root,1);
        return ans;
    }
};

或者按照不同的想法，二叉树总层数=1(root) + 左右子树的最大深度，由此我们可以用另外一种方法的递归解决问题。

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

抛开 DFS，用 BFS 也可以比较轻松自然的应对“层数”问题。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);

        int depth=0;
        while(!q.empty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode* node=q.front();
                q.pop();
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
            depth++;
        }
        return depth;
    }
};

226.翻转二叉树

读完题后发现这道题的考察点与其说是翻转，不如说是交换左右孩子，最简单的直接递归即可。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

同样的思路，我们用 BFS 也能完成，只不过稍显繁琐

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){
            TreeNode* node=q.front();
            q.pop();
            swap(node->left,node->right);
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
        return root;
    }
};

101. 对称二叉树

本题要求检查二叉树是否轴对称，最直观的思路十分简单，分别遍历二叉树的左右子树，然后比较是否一致即可。

轻轻松松偷大懒，就是占的空间有亿些多（

class Solution {
public:
    void preorder(TreeNode* root,vector<int>& res){
        if(root==nullptr) {
            res.push_back(200);
            return;
        }
        res.push_back(root->val);
        preorder(root->left,res);
        preorder(root->right,res);
    }
    void ppreorder(TreeNode* root,vector<int>& res){
        if(root==nullptr) {
            res.push_back(200);
            return;
        }        
        res.push_back(root->val);
        ppreorder(root->right,res);
        ppreorder(root->left,res);
    }
    bool isSymmetric(TreeNode* root) {
        vector<int> res_left;
        vector<int> res_right;
        preorder(root->left,res_left);
        ppreorder(root->right,res_right);
        return res_left==res_right;
    }
};

偷鸡解法看完了来看正经解法，我们只需要分别比较左右子树的对称点是否一致即可（也即left<->right)，也可以用递归轻松解决

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

此外，题目还要求我们给出一版迭代的写法，思路类似，用上 BFS 来写：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<pair<TreeNode*,TreeNode*>> q;
        q.push({root->left,root->right});
        while(!q.empty()){
            auto [left,right]=q.front();
            q.pop();
            if (left == nullptr && right == nullptr)
                continue;

            if (left == nullptr || right == nullptr)
                return false;

            if (left->val != right->val)
                return false;
            
            q.push({left->left,right->right});
            q.push({left->right,right->left});
        }
        return true;
    }
};

543. 二叉树的直径

二叉树的直径被定义为二叉树任意两节点间最远的距离，分析一下发现其实就是左右子树的最大深度之和，所以直接套用前面求二叉树深度中递归的方法（该方法求出了左右子树的最大深度），然后加和即可

class Solution {
public:
    int ans=0;
    int depth(TreeNode* root){
        if(!root) return 0;
        int depthL=depth(root->left);
        int depthR=depth(root->right);
        ans=max(depthL+depthR,ans);
        return max(depthL,depthR)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return ans;
    }
};

108. 将有序数组转换为二叉搜索树

本题要求将有序数组转换为平衡二叉搜索树，给出的数组是按升序排好的数组。对于本题，思路是找到中点，然后两边分别找中点，然后往树上挂以达到平衡

class Solution {
public:
    TreeNode* build(vector<int>& nums,int left,int right){
        if(left>right) return nullptr;
        int mid=left+(right-left)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=build(nums,left,mid-1);
        root->right=build(nums,mid+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums,0,nums.size()-1);
    }
};