文章目录
一、 二叉树结构体1.1 生成一个二叉树
二、求最大深度2.1 递归求最大深度2.2 之前我们写过层序遍历，多少层就是最大深度，借助linkedList
一、 二叉树结构体
public class TreeNode {
private String val
;
private TreeNode left
;
private TreeNode right
;
TreeNode(String x
) {
val
= x
;
}
public String
getVal() {
return val
;
}
public TreeNode
getLeft() {
return left
;
}
public TreeNode
getRight() {
return right
;
}
public TreeNode(String val
, TreeNode left
, TreeNode right
) {
this.val
= val
;
this.left
= left
;
this.right
= right
;
}
}
1.1 生成一个二叉树
public static TreeNode
oneGetter() {
TreeNode d
= new TreeNode("D", new TreeNode("C", null
, null
), new TreeNode("E", null
, null
));
TreeNode b
= new TreeNode("B", new TreeNode("A", null
, null
), d
);
TreeNode i
= new TreeNode("I", new TreeNode("H", null
, null
), null
);
TreeNode g
= new TreeNode("G", null
, i
);
TreeNode root
= new TreeNode("F", b
, g
);
return root
;
}
二、求最大深度
2.1 递归求最大深度
时间复杂度： 我们每个结点只访问一次，因此时间复杂度为 O(N)O(N)， 其中 NN 是结点的数量。
空间复杂度： 在最糟糕的情况下，树是完全不平衡的，例如每个结点只剩下左子结点，递归将会被调用 NN 次（树的高度），因此保持调用栈的存储将是 O(N)O(N)。但在最好的情况下（树是完全平衡的），树的高度将是 \log(N)log(N)。因此，在这种情况下的空间复杂度将是 O(\log(N))O(log(N))。
public static int diGuiMaxDeep(TreeNode root
) {
if (root
== null
) {
return 0;
} else {
int leftDeep
= diGuiMaxDeep(root
.getLeft());
int rightDeep
= diGuiMaxDeep(root
.getRight());
return Math
.max(leftDeep
, rightDeep
) + 1;
}
}
2.2 之前我们写过层序遍历，多少层就是最大深度，借助linkedList
public static int cengMaxDeep(TreeNode root
) {
int maxDeep
= 0;
if (root
== null
) {
return 0;
}
LinkedList
<TreeNode> linkedList
= new LinkedList<>();
linkedList
.add(root
);
TreeNode one
;
while (linkedList
.size()>0) {
maxDeep
++;
int oneCengLen
= linkedList
.size();
while (oneCengLen
> 0) {
one
= linkedList
.pop();
if(one
!=null
){
if(one
.getLeft()!=null
){
linkedList
.add(one
.getLeft());
}
if(one
.getRight()!=null
){
linkedList
.add(one
.getRight());
}
}
oneCengLen
--;
}
}
return maxDeep
;
}
