描述

111. 二叉树的最小深度 - 力扣（Leetcode）

分析

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从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
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.util.LinkedList;
import java.util.Queue;

//111. 二叉树的最小深度
public class MinimumDepthOfBinaryTree111 {
	public static void main(String[] args){
		TreeNode root = MyUtils.buildTree(new Integer[]{3,9,20,null,null,15,7});
		System.out.println("这棵树的最小深度为" + new Solution().minDepth(root));
	}
	
}
class Solution {

	//递归
    public int minDepth1(TreeNode root) {
    	//结束点
    	if (root == null) {
    		return 0;
    	}
    	int leftDepth = minDepth(root.left);
    	int rightDepth = minDepth(root.right);
    	if (root.left == null) {
    		return rightDepth + 1;
    	}
    	if (root.right == null) {
    		return leftDepth + 1;
    	}
    	return Math.min(leftDepth, rightDepth) + 1;
    }

    //层序遍历
    public int minDepth(TreeNode root) {
    	//结束点
    	if (root == null) {
    		return 0;
    	}
    	int depth = 0, size = 0;
    	Queue<TreeNode> que = new LinkedList<>();
    	que.offer(root);
    	while(!que.isEmpty()){
    		size = que.size();
    		depth++;
    		TreeNode temp;
    		for (int i = 0; i < size; i++) {
    			temp = que.poll();
    			if (temp.left == null && temp.right == null) return depth;
    			if (temp.left != null) que.offer(temp.left);
    			if (temp.right != null) que.offer(temp.right);
    		}
    	}
    	return depth;
    }

}


class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	public TreeNode(){};
	public TreeNode(int val){this.val = val;}
	public TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}



class MyUtils {
	/**
	 *二叉树的构建
	 * int[] -> 二叉树
	 */
	 public static TreeNode buildTree(Integer[] arr) {
        return buildTreeHelper(arr, 0);
    }

    public static TreeNode buildTreeHelper(Integer[] arr, Integer index) {
        if (index >= arr.length || arr[index] == null) {
            return null;
        }

        TreeNode node = new TreeNode(arr[index]);

        node.left = buildTreeHelper(arr, 2 * index + 1);
        node.right = buildTreeHelper(arr, 2 * index + 2);

        return node;
    }

    /**
	 *	层序遍历
     */
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

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

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

总结