# Can take you off [data structure] Chengwang Chapter 9: binary tree 2

datastructurechengwangchapterbinary

Catalog

Preface

Basic operations of binary tree

Get the number of nodes in the tree

Get the number of leaf nodes

For the first K The number of layer nodes

Get the height of the binary tree

The detected value is val Does the element of exist

Judge whether a tree is a complete binary tree

# Basic operations of binary tree

### Get the number of nodes in the tree

Traversal thought code :

``````// Get the number of nodes in the tree
int count = 0;
public int size1(BTNode root){
if(root == null) {
return 0;
}
count ++;
count += size1(root.left);
count += size1(root.right);
return count;
}``````

Sub problem ideas :

``````// Sub problem ideas
public int size2(BTNode root){
if (root == null){
return 0;
}
return size2(root.left) + size2(root.right) + 1;
}``````

### Get the number of leaf nodes

Traversal ideas :

Traverse to the leaf node , Just let the counter ++

Leaf node :root.left == null && root.right == null

``````public int leafNodes(BTNode root){
int count = 0;
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
count++;
}
leafNodes(root.left);
leafNodes(root.right);
return count;
}``````

Sub problem ideas :

Left tree leaf node plus right tree leaf node

``````public int leafNodes(BTNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
return leafNodes(root.left) + leafNodes(root.right);
}``````

### For the first K The number of layer nodes

hypothesis K be equal to 3

That is to say A The third floor of

B,C The second floor of

D,E,F,G The first floor of

Termination conditions K be equal to 1

``````public int getKLeveLNodeCount(BTNode root, int k){
if(root == null || k <= 0){
return 0;
}
if(k == 1){
return 1;
}
return getKLeveLNodeCount(root.left,k - 1) + getKLeveLNodeCount(root.right ,k-1);
}``````

### Get the height of the binary tree

Sub problem ideas

The height of the left tree and the height of the right tree are the maximum , Then add 1 = The height of the whole tree

``````public int getHeight(BTNode root){
if(root == null){
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;``````

### The detected value is val Does the element of exist

`````` public BTNode find(BTNode root,char val){
if(root == null){
return null;
}
if(root.val == val){
return root;
}
BTNode ret = find(root.left,val);
if(ret != null){
return ret;
}
ret = find(root.right,val);
if(ret != null){
return ret;
}
return null;
}``````

### Judge whether a tree is a complete binary tree

``````public boolean getHeight3(BTNode root){
if (root == null) return true;
queue.offer(root);
while (!queue.isEmpty()){
BTNode cur = queue.poll();
if (cur != null){
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()){
BTNode ret = queue.peek();
if(ret != null){
return false;
}
queue.poll();
}
return true;
}``````