The Java implementation finds the depth and width of the binary tree
- 2020-04-01 03:56:27
- OfStack
This is a common binary tree operation. To summarize:
Set the data structure of the node as follows:
class TreeNode {
char val;
TreeNode left = null;
TreeNode right = null;
TreeNode(char _val) {
this.val = _val;
}
}
1. Binary tree depth
In this case, we can use recursion to find the depth of the left subtree and the depth of the right subtree respectively. The larger value of the two depths is +1.
//Gets the maximum depth
public static int getMaxDepth(TreeNode root) {
if (root == null)
return 0;
else {
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
return 1 + Math.max(left, right);
}
}
2. Binary tree width
Using queues, the binary tree is traversed hierarchically. After traversing the previous layer, all the nodes of the next layer have been put into the queue, and the number of elements in the queue is the width of the next layer. The maximum width of the binary tree can be obtained by traversing the next layer in turn.
//Gets the maximum width
public static int getMaxWidth(TreeNode root) {
if (root == null)
return 0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
int maxWitdth = 1; //Maximum width
queue.add(root); //The team
while (true) {
int len = queue.size(); //The number of nodes in the current layer is
if (len == 0)
break;
while (len > 0) {//If the current layer, there are also nodes
TreeNode t = queue.poll();
len--;
if (t.left != null)
queue.add(t.left); //Next layer node enqueue
if (t.right != null)
queue.add(t.right);//Next layer node enqueue
}
maxWitdth = Math.max(maxWitdth, queue.size());
}
return maxWitdth;
}