P104

发表于 | 分类于 |

LeetCode P104 Maximum Depth of Binary Tree 题解

1.题目：

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Subscribe to see which companies asked this question

题意：

找出一个二叉树最长一个分支上面节点的个数

2.解题思路:

首先了解二叉树，在纸上画出图形，然后选择一个遍历方法，我选择的是深度优先。
然后开始遍历，确定一个遍历方式，我选择的是先左后右。
以下面这个二叉树为例测试：
测试二叉树数据

3.代码

[title] [] [url] [link text]
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
 
package leetcode;

import tool.TreeNode;

/**
 * 
 * @author ZhangMengRou
 *
 */
public class p104 {

	static int max = 0;
	static int count = 1;

	public static void main(String[] args) {
		// Scanner in = new Scanner(System.in);
		// String a = in.nextLine();
		String a = "12324546#5##3##6##";
		StringBuilder bu = new StringBuilder();
		bu.append(a);
		TreeNode froot = null;
		froot = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		TreeNode n6 = new TreeNode(6);
		TreeNode n7 = new TreeNode(7);
		froot.left = n2;
		froot.right = n3;
		n2.left = n4;
		n2.right = n5;
		n4.left = n6;
		n6.right = n7;
		int ans = maxDepth(froot);
		System.out.print(ans);
	}

	public static int maxDepth(TreeNode root) {

		// if (root != null) {
		DFS(root);
		int ans = max;

		return ans;
		// } else {
		// return 0;
		// }
	}

	public static void DFS(TreeNode t) {
		// System.out.print("mmmm "+t.val+"  "+count+"\n");
		if (t == null) {
			return;
		}
		if (!(t.left == null)) {
			count++;

			DFS(t.left);
		}

		if (!(t.right == null)) {
			count++;

			DFS(t.right);
		}
		if (max < count) {
			max = count;
		}
		count--;

		return;
	}

}


//
//public class TreeNode {
//
//		public int val;
//	    public TreeNode left;
//	    public TreeNode right;
//	    public TreeNode(int x) { val = x; }
//	
//}


4.一些总结：

希望可以找到什么方法优化二叉树的输入TUT