CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第十六天｜222-111-104

Posted on

LeetCode 104. 二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxDepth(TreeNode root) {
        return postorder(root);
    }

    private int postorder (TreeNode node) {

        if (node == null) {
            return 0;
        } else {
            // to some extent, this is post-order, LRD traversal
            return Math.max(postorder(node.left), postorder(node.right)) + 1;
        }

    }
}

没什么难度，后序遍历就行了

LeetCode 111.二叉树的最小深度

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
class Solution {
    public int minDepth(TreeNode root) {
        return postorder(root);
    }

    private int postorder (TreeNode node) {

        // recursion exits when node is empty
        if (node == null) {
            return 0;
        }

        if (node.left != null && node.right == null) {
            return postorder(node.left);
        }

        if (node.left == null && node.right != null) {
            return postorder(node.right);
        }

        // the else case means either this node is a leaf node or it has two children
        return Math.min(postorder(node.left), postorder(node.right)) + 1;


    }
}

注意单枝节点

LeetCode 222.完全二叉树的节点个数

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// class Solution {
//     public int countNodes(TreeNode root) {

//         if (root == null) {
//             return 0;
//         }

//         TreeNode node = root;
//         Queue<TreeNode> queue = new LinkedList();
//         queue.add(node);
//         int cnt = 0;

//         while(!queue.isEmpty()) {
//             int size = queue.size();

//             for (int i = 0; i < size; i++) {
//                 node = queue.poll();
//                 cnt++;

//                 if (node.left != null) {
//                     queue.add(node.left);
//                 }

//                 if (node.right != null) {
//                     queue.add(node.right);
//                 }
//             }
//         }

//         return cnt;
//     }
// }

class Solution {

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }


        TreeNode left = root.left;
        int leftDepth = 0;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }


        TreeNode right = root.right;
        int rightDepth = 0;
        while (right != null) {
            right = right.right;
            rightDepth++;
        }

        // if it is a full binary tree, easy culculation 
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        }else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }

    }
    
}

第一种方法是遍历所有节点数数，O(n)， 第二种方法利用完全二叉树的特性，完全二叉树一定包含满二叉树，而满二叉树的节点数量易于计算。