二叉树的最大深度

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode 104. Maximum Depth of Binary Tree

递归

1
2
3
4
5
6
7
8
9
10
int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftTree = maxDepth (root->left);
        int rightTree = maxDepth (root->right);
        
        return max (leftTree, rightTree) + 1;
        
    }

当前节点的最大深度 = 左右子树最大深度的较大者 + 1

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int maxDepth (TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    queue<TreeNode*> level;
    level.push(root);
    int depth = 0;
    while (!level.empty()) {
        depth++;

        int n = level.size();

        for (int i = 0; i < n; i++) {
            TreeNode* node = level.front();
            level.pop();
            if (node->left != nullptr) {
                level.push(node->left);
            }
            if (node->right != nullptr) {
                level.push(node->right);
            }
        }
    }

    return depth;
}

迭代时间8ms 明显 优于 递归的24ms

0%