还是树~

102. Binary Tree Level Order Traversal

Analysis

大名鼎鼎的 bfs。

Code

bfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        queue<TreeNode*> q;
        q.push(root);
        int cnt = 1;
        while(!q.empty()) {
            vector<int> tmp;
            TreeNode *node;
            int sum = 0;
            for(int i = 0; i < cnt; i++) {
                node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left) {
                    q.push(node->left);
                    sum++;
                }
                if(node->right) {
                    q.push(node->right);
                    sum++;
                }
            }
            cnt = sum;
            ret.push_back(tmp);
        }
        return ret;
    }
};

因为题目要求按层输出结点，所以一次性要遍历完一层的所有结点，就需要提前将下一层的结点个数计算出来，这样才能保证最终得到的结果符合题意。实际上，在开始循环之前，队列的大小就是当前层的结点个数，也就可以写成这样：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            vector<int> tmp;
            TreeNode *node;
            int cnt = q.size();
            for(int i = 0; i < cnt; i++) {
                node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

这样写，看着会清爽很多。

dfs

既然 bfs 能解决这个问题，同样 dfs 也可以解决这个问题。

class Solution {
public:
    void dfs(vector<vector<int>>& ret, TreeNode *root, int level) {
        if(ret.size() < level + 1) ret.push_back(vector<int>());
        ret[level].push_back(root->val);
        if(root->left) dfs(ret, root->left, level + 1);
        if(root->right) dfs(ret, root->right, level + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        dfs(ret, root, 0);
        return ret;
    }
};

实际上，这里用到的 dfs 就是二叉树的先序遍历，但这里的关键在于，要按照层数来访问结点，同时在访问结点前，需要提前创建好数组。

104. Maximum Depth of Binary Tree

Analysis

求二叉树的深度，em，这个题依然可以从 dfs 和 bfs 两个方向入手。

Code

dfs

先从 dfs 入手。

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

当然了，也可以这样写：

class Solution {
public:
    void dfs(TreeNode *root, int depth, int &maxdepth) {
        if(depth > maxdepth) maxdepth = depth;
        if(root->left) dfs(root->left, depth + 1, maxdepth);
        if(root->right) dfs(root->right, depth + 1, maxdepth);
    }
    int maxDepth(TreeNode* root) {
        int maxdepth = 0;
        if(root) dfs(root, 1, maxdepth);
        return maxdepth;
    }
};

看着清爽了一些？
其实，这个还可以写的更夸张😂，如下：

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

前面写的递归的思路本质上还是遍历二叉树的思路，但这样写的思路是基于分治的，二叉树的高度就是左右子树的高度加 1，所以只需要不断的去计算子树的高度再返回加 1 就可以得到整个树的高度了。

bfs

二叉树的深度对应的就是二叉树的层数。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int maxdepth = 0;
        if(!root) return maxdepth;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *node;
            int cnt = q.size();
            for(int i = 0; i < cnt; i++) {
                node = q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            maxdepth++;
        }
        return maxdepth;
    }
};

101. Symmetric Tree

Analysis

判断一棵二叉树是否对称，这个题显然要用 dfs 来做。

Code

dfs

判断二叉树是否对称，实际上就是要判断左右子树是不是一样的，所以使用 2 个指针递归的去判断即可。

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

注意，一开始递归的时候不要直接写check(root, root)，这样就多判断了一遍，因为第一次递归中check(root1->left, root2->right)和check(root1->right, root2->left)是一样的。

bfs

同样，这个题也可以用 bfs 来做。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        TreeNode *u, *v;
        while(!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if(!u && !v) continue;
            if((!u || !v) || (u->val != v->val)) return false;
            q.push(u->left);
            q.push(v->right);
            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }
};

同样，第一次入队的时候直接将左右子结点入队。

Summary

3 个树的相关题目，做的挺有意思的。有关二叉树的题，有时候用 dfs 做很简单，有时候用 bfs 做很简单，所以，最好是能合理的选择最简单的方法完成。当然，也不排除可能面试时要用特定的方法写，所以最好还是都会比较好。