题解 | #二叉树的最大深度#

深度优先搜索--非递归

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    //dfs
    int maxDepth(TreeNode* root) {
        // write code here

        return dfs(root); //100%
    }
    int dfs(TreeNode* root) {
        if (!root) return 0;
        map<TreeNode*, bool> m;
        stack<TreeNode*> s;
        s.push(root);
        m[root] = true;
        int max = s.size();
        while (!s.empty()) {
            TreeNode* cur = s.top();
            if (cur->left && m.find(cur->left) == m.end()) {
                s.push(cur->left);
                m[cur->left] = true;
                continue;
            }
            if (cur->right && m.find(cur->right) == m.end()) {
                s.push(cur->right);
                m[cur->right] = true;
                continue;
            }
            //回溯
            max = s.size() > max ? s.size() : max;
            do {
                s.pop();
                cur = s.top();
            } while (!s.empty() &&
                m.find(cur->left) != m.end() &&
                m.find(cur->right) != m.end());
        }
        return max;
    }
};

广度优先搜索--非递归

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    //dfs
    int maxDepth(TreeNode* root) {
        // write code here
        return bfs(root); //100%
    }
    int bfs(TreeNode* root){
        if (!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int count = 0;
        while(!q.empty()){
            int sz = q.size();
            for(int i=0; i<sz; ++i){
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            count++;
        }
        return count;
    }

};