描述

104. 二叉树的最大深度 - 力扣（Leetcode）

分析

实现

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
import java.lang.Math;
import java.util.Queue;
import java.util.LinkedList;

//104. 二叉树的最大深度
public class MaximumDepthOfBinaryTree104 {
	public static void main(String[] args){
		Integer[] arr = {3,9,20,null,null,15,7};
		TreeNode root = MyUtils.buildTree(arr);
		System.out.println(new Solution().maxDepth(root));
	}
	
}

class Solution {
	//递归 (我最喜欢的一个，简洁高效)
    public int maxDepth1(TreeNode root) {
    	if(root == null){
    		return 0;
    	}
    	int leftDepth = maxDepth(root.left);
    	int rightDepth = maxDepth(root.right);
    	return Math.max(leftDepth, rightDepth) + 1;
    }
    //用层序遍历
    public int maxDepth2(TreeNode root) {
    	if (root == null) {
    		return 0;
    	}
    	Queue<TreeNode> que = new LinkedList<>();
    	que.offer(root);
    	int res = 0, size = 0;
    	while(!que.isEmpty()){
    		size = que.size();
    		res++;
    		TreeNode temp;

    		for(int i = 0; i < size; i++){
    			temp = que.poll();
    			if(temp.left != null) que.offer(temp.left);
    			if(temp.right != null) que.offer(temp.right);
    		}
    	}
    	return res;
    }
    //n叉树递归 
    public int maxDepth3(Node root) {
    	if(root == null){
    		return 0;
    	}
    	int depth = 0;
    	if (root.children != null) {
    		for (Node child : root.children) {
    			depth = Math.max(depth,maxDepth(child));
    		}
    	}
    	return depth + 1;
    }
    //n叉树 层序遍历
    public int maxDepth4(Node root){
    	if (root == null) {
    		return 0;
    	}
    	Queue<Node> que = new LinkedList<>();
    	int depth = 0, size = 0;
    	que.offer(root);
    	while(!que.isEmpty()){
    		size = que.size();
    		depth++;
    		Node temp;
    		for (int i = 0; i < size; i++) {
    			temp = que.poll();
    			if (temp.children != null) {
    				for (Node child : temp.children) {
    					if (child != null) {
    						que.offer(child);
    					}
    				}
    			}
    		}
    	}

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

总结