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

二叉树的最大深度

http://www.nowcoder.com/questionTerminal/8a2b2bf6c19b4f23a9bdb9b233eefa73

深度优先搜索--非递归

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;
    }

};
全部评论

相关推荐

身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
06-02 15:53
阳光学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务