有关二叉树 的基本操作

二叉树第二部分

这一部分 完成 一些有关二叉树 的基本操作

// 前序遍历
void preOrderTraversal(Node root);

// 中序遍历
void inOrderTraversal(Node root);

// 后序遍历
void postOrderTraversal(Node root);

// 遍历思路-求结点个数
static int size = 0;
void getSize1(Node root);

// 子问题思路-求结点个数
int getSize2(Node root);

// 遍历思路-求叶子结点个数
static int leafSize = 0;
void getLeafSize1(Node root);

// 子问题思路-求叶子结点个数
int getLeafSize2(Node root);

// 子问题思路-求第 k 层结点个数
int getKLevelSize(Node root);

// 获取二叉树的高度
int getHeight(Node root);

// 查找 val 所在结点，没有找到返回 null
// 按照 根 -> 左子树 -> 右子树的顺序进行查找
// 一旦找到，立即返回，不需要继续在其他位置查找
Node find(Node root, int val);

这里前中后续遍历 上文 已经完成.

1.求结点个数

1.遍历思路

  //遍历思路
     int size = 0;
    void getSize1(TreeNode root) {
    
        if(root == null) {
    
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

2.子问题思路

   //子问题思路
    int getSize2(TreeNode root) {
    
        if(root == null) {
    
            return 0;
        }
        return getSize2(root.left) + getSize2(root.right) + 1;
    }

2.求叶子结点个数

1.遍历思路

 // 遍历思路-求叶子结点个数
     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.子问题思路

  // 子问题思路-求叶子结点个数
    int getLeafSize2(TreeNode root) {
    
        if(root == null) {
    
            return 0;
        }
        if(root.left == null && root.right == null) {
    
            // 当前 的 root 为 叶子节点
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);

    }

3求第k层结点个数

这里直接来看子问题思路

子问题思路-求第 k 层结点个数

  // 子问题思路-求第 k 层结点个数
    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.获取二叉树的高度

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

上面的看不懂 也可以看这种 一个 思路递归下来
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;
    }

二叉树的最大深度 上面的oj题

5.查找二叉树中是否存在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;
        //这里可以简写成这样
        return find(root.right,val);
    }

这里 也没啥 难度 只需要 知道两个 边界条件就ok 那就是 root == null 和 root.val == val 然后 去 递归左子树 和 右子树 ，判断

root.val 是否等于 val 即可

注意 这里 我们使用 这个方法是 主函数 中要 使用try 和 catch

因为 没有查找的val 会返回 null此时 使用 会发生空指针异常

   try{
    
                 TreeNode treeNode1 =  binaryTree.find(treeNode,'A');
                 System.out.println(treeNode1.val);
             }catch(NullPointerException e) {
    
                 e.printStackTrace();
                 System.out.println("捕获到空指针异常");
             }

6. 判断一课树 是否是完全二叉树

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;
    }