Basic operations on binary tree

The second part of a binary tree

This part complete Something about binary trees Basic operation

//  The former sequence traversal 
void preOrderTraversal(Node root);

//  In the sequence traversal 
void inOrderTraversal(Node root);

//  After the sequence traversal 
void postOrderTraversal(Node root);

//  Traversal ideas - Find the number of nodes 
static int size = 0;
void getSize1(Node root);

//  Sub problem ideas - Find the number of nodes 
int getSize2(Node root);

//  Traversal ideas - Find the number of leaf nodes 
static int leafSize = 0;
void getLeafSize1(Node root);

//  Sub problem ideas - Find the number of leaf nodes 
int getLeafSize2(Node root);

//  Sub problem ideas - Please  k  Number of layer nodes 
int getKLevelSize(Node root);

//  Get the height of the binary tree 
int getHeight(Node root);

//  lookup  val  Node , No return found  null
//  according to   root  ->  The left subtree  ->  Search in the order of right subtree 
//  Once found , Return immediately , There is no need to continue looking elsewhere 
Node find(Node root, int val);

Here, the previous, middle and subsequent iterations Above, Already completed .

1. Find the number of nodes

1. Traversal ideas

  // Traversal ideas 
     int size = 0;
    void getSize1(TreeNode root) {
    
        if(root == null) {
    
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

2. Sub problem ideas

   // Sub problem ideas 
    int getSize2(TreeNode root) {
    
        if(root == null) {
    
            return 0;
        }
        return getSize2(root.left) + getSize2(root.right) + 1;
    }

2. Find the number of leaf nodes

1. Traversal ideas

 //  Traversal ideas - Find the number of leaf nodes 
     int leafSize = 0;
    void getLeafSize1(TreeNode root) {
    
        if(root == null) {
    
            return;
        }
        if(root.left == null && root.right == null) {
    
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
  }

2. Sub problem ideas

  //  Sub problem ideas - Find the number of leaf nodes 
    int getLeafSize2(TreeNode root) {
    
        if(root == null) {
    
            return 0;
        }
        if(root.left == null && root.right == null) {
    
            //  At present   Of  root  by   Leaf node 
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);

    }

3 Please k Number of layer nodes

Here, let's look directly at the thinking of the sub problem

Sub problem ideas - Please k Number of layer nodes

  //  Sub problem ideas - Please  k  Number of layer nodes 
    int getKLevelSize(TreeNode root,int k) {
    
            if(root == null || k < 0) {
    
                return 0;
            }
            if(k == 1) {
    
                return 1;
            }
            return getKLevelSize(root.left,k - 1) + getKLevelSize(root.right,k-1);
    }

4. Get the height of the binary tree

 int getHeight(TreeNode root) {
    
        return root == null?0:Math.max(getHeight(root.left)+1,getHeight(root.right)+1);
    }

 I can't understand the above   You can also watch this   One   Train of thought recurs down 
int getHeight2(TreeNode root) {
    
        if(root == null) {
    
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

The maximum depth of a binary tree above oj topic

5. Find out if there is... In the binary tree val

TreeNode find(TreeNode root, char val) {
    
        if(root == null) return null;
        if(root.val == val) {
    
            return root;
        }
// TreeNode top = find(root.left,val);
// if(top != null) {
    
// return top;
// }
// TreeNode top2 = find(root.right,val);
// if(top2 != null ) {
    
// return top2;
// }
// return null;
        // It can be abbreviated as 
        return find(root.right,val);
    }

here Also do not have what difficulty It only needs Know two Boundary condition ok That's it root == null and root.val == val then Go to Recursive left subtree and Right subtree , Judge

root.val Is it equal to val that will do

Be careful here We use The method is The main function Zhongyao Use try and catch

because Nothing to look for val Returns the null here Use Null pointer exception occurs

   try{
    
                 TreeNode treeNode1 =  binaryTree.find(treeNode,'A');
                 System.out.println(treeNode1.val);
             }catch(NullPointerException e) {
    
                 e.printStackTrace();
                 System.out.println(" Null pointer exception caught ");
             }

6. Judge a lesson tree Whether it is a complete binary tree

boolean isCompleteTree(TreeNode root){
    
        if(root == null) {
    
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
    
            TreeNode top = queue.poll();
            if(top != null) {
    
                queue.offer(root.left);
                queue.offer(root.right);
            }else {
    
                break;
            }
            while(!queue.isEmpty()) {
    
                TreeNode top2 = queue.peek();
                if(top != null) {
    
                    return false;
                }
                queue.poll();
            }
        }
        return true;
    }