【JAVA数据结构】二叉树的常用方法(你想要的这里都有)

千万人中，万幸得以相逢

大家好，这里是新一，请多关照🙈🙉🙊。在本篇博客中，新一将会为大家介绍数据结构与算法之二叉树方法篇，二叉树有许多依托遍历的常用方法，这些方法对于我们弄懂二叉树有很大的帮助，为了方便大家理解，新一特地给大家附上了 源码和图片 便于大家理解，干货满满哟。（以下结果均在IDEA中编译）希望在方便自己复习的同时也能帮助到大家。😜😜😜🎪🚀🧰

以下是我们的文章

---

---

🎪 二叉树常用方法实现

以上是我们要实现的方法二叉树用例，在这里新一先不用正式的方法构造一颗二叉树，二叉树的构造(内部类)我们在后续博客中说明，这里我们先临时构造一棵二叉树，如下：

public class BinaryTree {
    public TreeNode root;//二叉树的根节点

    public TreeNode createTree() {//暂时写法
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
}

我们要实现的方法如下：

1.1 🚀 获取树中节点个数

public int size2(TreeNode root){
        if (root == null){//判空
            return 0;
        }
        //递归遍历左右树
        return size2(root.left) + size2(root.right) + 1;
    }

1.2 🚀 获取叶子节点个数

public int getLeafNodeCount1(TreeNode root){
        if (root == null){//判空则返回0
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;//叶节点返回1
        }
        //递归遍历左右树
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

1.3 🚀 求第K层节点个数

public int getLeafNodeCount2(TreeNode root, int k){
        if (root == null){//空返回0
            return 0;
        }
        if (k == 1){
            return 1;//递归访问k - 1后到达指定层数返回1
        }
        return getLeafNodeCount2(root.left, k - 1) + getLeafNodeCount2(root.right, k - 1);
    }

1.4 🚀 获取二叉树的高度

//时间复杂度O(n)，空间复杂度O(log2(n))
    public int getHight(TreeNode root){
         if (root == null){//判空
             return 0;
         }
         //尽量不要用三目运算符 - 比较左右树最大高度
         return Math.max(getHight(root.left),getHight((root.right))) + 1;
    }

1.5 🚀 检测值为value的元素是否存在

public TreeNode find2(TreeNode root, char val){
        if (root == null){//为空不存在返回null
            return null;
        }
        if (root.val == val){
            return root;//找到节点
        }
        TreeNode ret = find2(root.left, val);//遍历左树
        if (ret != null){
            return ret;
        }else{//左树为空，遍历右树
            return find2(root.right, val);
        }
    }

1.6 🚀 判断一棵树是不是完全二叉树

public boolean  isCompleteTree(TreeNode root){
        if (root == null){//空树也为完全二叉树
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();//队列
        queue.offer(root);//根节点入队
        while (queue.peek() != null){
            TreeNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while (!queue.isEmpty()){
            if (queue.peek() != null){
                return false;
            }
            queue.poll();
        }
        return queue.isEmpty();
    }

1.7 🚀 层序遍历

public void levelOrder(TreeNode root){
        if (root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.peek() != null){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");//打印每层节点
            if (cur != null){
                if (cur.left != null) {//不为空入队
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
    }