【数据结构】二叉树（中）

思路1：（遍历思路） 利用遍历思路来获取总结点，那么当root != null 时，说明该节点有值，可以被记录，之后利用递归调用来遍历子树的各个节点。

int count = 0;
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }

思路2：（子问题思路） 一颗二叉树的结点数，总是等于该树中的节点加上该节点的左子树的节点数与右子树的节点数之和，同样可以利用递归实现

public int size1(TreeNode root){
        if(root == null){
            return 0;
        }
        return size1(root.left) + size1(root.right) + 1;
    }

思路：（遍历思路）判断条件是,当该节点的左树与右树均为空时，该节点为叶子节点。

         int size = 0;
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            size++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return size;
    }

思路：从根节点的左树与右树分别找，最后叶子节点的个数等于根节点左树的叶子节点+右树叶子节点。

public int getLeafNodeCount1(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

思路：（子问题思路）根节点为第3层，从上往下依次递减，当K == 1时，就是所要求的那层，最后记录该层节点的个数（左树第三层节点数+右树该层节点数）。

public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }

思路：（子问题思路）首先记录左树的高度，随后记录右树的高度，之后将左树的高度与右树的高度比大小，并让最大的树的高度+1（利用三目运算符实现）。

 public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return leftH > rightH ? leftH+1 : rightH+1;
    }

思路：首先判断根节点是否为空，其次判断根节点的数值是否与被检测元素相等；

接收左树与右树的返回值，该返回值如果是null,说明该左树或者右树没有遍历的结果；如果不为空，说明该左树或者右树有遍历的结果，结果用ret接收。

public TreeNode find(TreeNode root, int val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode ret = find(root.left,val);
        if(ret != null){
            return ret;
        }
        ret = find(root.right,val);
        if(ret != null){
            return ret;
        }
        return ret;
    }

思路：层序遍历用队列实现，先将根节点放入队列，然后出队列，用某一个节点去接收出队列的元素，并用该节点去访问其左树与右树，当队列为空时，说明二叉树层序遍历结束。

public void levelOrder(TreeNode root){
       Queue queue = new LinkedList<>();
        if(root == null){
            return;
        }
        queue.offer(root);
        while (! queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+"   ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

思路： 根据层序遍历的思路，将所有节点的左树与右树放入队列中；

           与此同时，也将队列元素依次取出存入到cur中，并判断cur 是否拿到 null,如果拿到就跳出循环，否则循环继续；

            出循环之后，说明cur 拿到 null 了，此时队列中要么全是null（注意队列里面全是null 时，此时队列不为空） ,要么既有null 也有非空数值，就要重新对队列进行循环，如果队列为空时，新的cur 拿到的全是null ,说明该树是完全二叉树，否则不是完全二叉树。

 boolean isCompleteTree(TreeNode root){
       Queue queue = new LinkedList<>();
       if(root == null){
           return false;
       }
       queue.offer(root);
       while (!queue.isEmpty()) {
           TreeNode cur = queue.poll();
           if (cur == null) {
               break;
           } else {
               queue.offer(cur.left);
               queue.offer(cur.right);
           }
       }
       //  二次遍历队列看里面是否都是null , 是返回true;否则返回false
 //      while (!queue.isEmpty()){
 //          TreeNode cur = queue.poll();
 //           if(cur != null){
 //              return  false;
 //          }
 //     }
         while (!queue.isEmpty()){
            TreeNode cur = queue.peek();
            if(cur == null){
                queue.poll();
            }else {
                return false;
            }
        }
        return true;
    }