explain:
The depth of the binary tree: A path to the tree is formed from the root node to the node (including root and leaf node) that passes by the leaf node in turn. The length of the longest path is the depth of the tree.
Width of a binary tree: Each layer of a binary tree has a certain number of nodes. The number of nodes in the layer with the largest number of nodes is called the width of the binary tree.
Idea: Recursive implementation.
1. Each node can be regarded as a root node
2. The depth of the root node (any node) is equal to its left or right subtree depth maximum +1
3. Start traversing from the root node. If you traversing to the leaf node, the depth is 0
//The depth of the binary tree public static int Depth(node root){ if(root == null){ return 0; } int dl = Depth(root.leftchild); int dr = Depth(root.rightchild); return dl>dr? dl+1:dr+1; }2. The width of the binary tree
Idea: Add a counter during layer sequence traversal to record the number of nodes in each layer
1. When each layer is out of the queue, the number of nodes in the next layer is actually the Size() of the queue.
2. At the end of each layer traversal, compare the maximum width with the current number of nodes and record the maximum value.
public static int Width(node root) {if(root == null) return 0;Queue<node> q = new LinkedList<node>();q.add(root);int width = 1;//Maximum width int len = 1;//The current number of nodes on the layer while(q.size()>0){while(len-->0){node node = q.poll();if(node.leftchild != null){q.add(node.leftchild);}if(node.rightchild != null){q.add(node.rightchild);}}len = q.size();//After each layer's loop ends, record the number of nodes in the next layer width = width>q.size() ? width : q.size();}return width;}Summarize
The above is all about the Java language description of the depth and width of the binary tree. I hope it will be helpful to everyone. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!