【java-数据结构】别再死磕理论！这些 Java 二叉树题目带你快速上手

学无止尽5

发布于 2025-03-01 21:27:27

12510

代码可运行

文章被收录于专栏：C 与 Java 数据结构研习志C 与 Java 数据结构研习志

运行总次数：0

代码可运行

前言

在Java编程的世界里，许多初学者常常陷入理论的迷宫，对着复杂的二叉树理论死磕，却忽略了实践的力量。其实，理论固然重要，但通过实际的题目练习，能更高效地掌握二叉树的相关知识。别再让晦涩的理论束缚你的脚步，那些看似复杂的二叉树概念，在实际题目中往往能变得清晰易懂。这里精心挑选了一系列Java二叉树题目，从基础的遍历到复杂的算法应用，让你在实战中快速上手，轻松跨越理论与实践的鸿沟，开启二叉树编程的新旅程。

1、检查两棵树是否相同。—题目链接

题目详解代码

package Demo2_25;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-25
 * Time:19:13
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if ((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main(String[] args) {
        // 创建第一棵二叉树
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);

        // 创建第二棵相同的二叉树
        TreeNode q = new TreeNode(1);
        q.left = new TreeNode(2);
        q.right = new TreeNode(3);

        // 创建 Solution 类的实例
        Solution solution = new Solution();

        // 调用 isSameTree 方法判断两棵树是否相同
        boolean result = solution.isSameTree(p, q);

        // 输出结果
        System.out.println("两棵树是否相同: " + result);

        // 创建一棵不同的二叉树
        TreeNode r = new TreeNode(1);
        r.left = new TreeNode(3);
        r.right = new TreeNode(2);

        // 再次调用 isSameTree 方法判断
        boolean differentResult = solution.isSameTree(p, r);
        System.out.println("两棵树是否相同: " + differentResult);
    }
}

2、另⼀棵树的⼦树。—题目链接

题目详解代码：

package Demo2_25;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-25
 * Time:19:49
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution1 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree(root.left, subRoot)) {
            return true;
        }
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if ((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }


    public static void main(String[] args) {
        // 创建主树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(4);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(2);

        // 创建子树
        TreeNode subRoot = new TreeNode(4);
        subRoot.left = new TreeNode(1);
        subRoot.right = new TreeNode(2);

        // 创建 Solution 类的实例
        Solution1 solution = new Solution1();

        // 调用 isSubtree 方法判断主树中是否包含子树
        boolean result = solution.isSubtree(root, subRoot);

        // 输出结果
        System.out.println("主树中是否包含子树: " + result);
    }
}

3、翻转⼆叉树。 —题目链接

题目详解代码

package Demo2_25;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-25
 * Time:19:58
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution2 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }


    public static void main(String[] args) {
        // 创建一棵二叉树
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        // 创建 Solution 类的实例
        Solution2 solution = new Solution2();

        // 调用 invertTree 方法翻转二叉树
        TreeNode invertedRoot = solution.invertTree(root);

        // 简单输出翻转后二叉树的根节点值
        if (invertedRoot != null) {
            System.out.println("翻转后二叉树的根节点值为: " + invertedRoot.val);
        } else {
            System.out.println("翻转后的二叉树为空。");
        }
    }
}

4、判断⼀棵⼆叉树是否是平衡⼆叉树。—题目链接

题目详解代码

package Demo2_25;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-25
 * Time:20:28
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution3 {
    public boolean isBalanced(TreeNode root) {
        //时间复杂度为N^2
//        if (root == null) {
//            return true;
//        }
//        int leftHeight = maxDepth(root.left);
//        int rightHeight = maxDepth(root.right);
//
//        return Math.abs(leftHeight - rightHeight) <= 1
//                && isBalanced(root.left)
//                && isBalanced(root.right);
//    }
//
//    public int maxDepth(TreeNode root) {
//        if (root == null) {
//            return 0;
//        }
//        int leftH = maxDepth(root.left);
//        int rightH = maxDepth(root.right);
//        return leftH > rightH ? leftH + 1 : rightH + 1;
//    }

        //时间复杂度为N
        if(root==null){
            return true;
        }
        return maxDepth(root)>=0;
    }
    public int maxDepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftH=maxDepth(root.left);
        if(leftH==-1){
            return -1;
        }
        int rightH=maxDepth(root.right);
        if(leftH>=0&&rightH>=0&&Math.abs(leftH-rightH)<=1){
            return Math.max(leftH,rightH)+1;
        }
        else{
            return -1;
        }
    }


    public static void main(String[] args) {
        // 创建一个平衡二叉树
        TreeNode balancedRoot = new TreeNode(3);
        balancedRoot.left = new TreeNode(9);
        balancedRoot.right = new TreeNode(20);
        balancedRoot.right.left = new TreeNode(15);
        balancedRoot.right.right = new TreeNode(7);

        // 创建一个不平衡二叉树
        TreeNode unbalancedRoot = new TreeNode(1);
        unbalancedRoot.left = new TreeNode(2);
        unbalancedRoot.right = new TreeNode(2);
        unbalancedRoot.left.left = new TreeNode(3);
        unbalancedRoot.left.right = new TreeNode(3);
        unbalancedRoot.left.left.left = new TreeNode(4);
        unbalancedRoot.left.left.right = new TreeNode(4);

        // 创建 Solution 类的实例
        Solution3 solution = new Solution3();

        // 测试平衡二叉树
        boolean isBalanced1 = solution.isBalanced(balancedRoot);
        System.out.println("第一棵树是否为平衡二叉树: " + isBalanced1);

        // 测试不平衡二叉树
        boolean isBalanced2 = solution.isBalanced(unbalancedRoot);
        System.out.println("第二棵树是否为平衡二叉树: " + isBalanced2);
    }
}

5、对称⼆叉树。—题目链接

题目详解代码

package Demo2_25;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-25
 * Time:21:20
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution4 {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if ((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }


    public static void main(String[] args) {
        // 创建一个对称的二叉树
        TreeNode symmetricRoot = new TreeNode(1);
        symmetricRoot.left = new TreeNode(2);
        symmetricRoot.right = new TreeNode(2);
        symmetricRoot.left.left = new TreeNode(3);
        symmetricRoot.left.right = new TreeNode(4);
        symmetricRoot.right.left = new TreeNode(4);
        symmetricRoot.right.right = new TreeNode(3);

        // 创建一个不对称的二叉树
        TreeNode asymmetricRoot = new TreeNode(1);
        asymmetricRoot.left = new TreeNode(2);
        asymmetricRoot.right = new TreeNode(2);
        asymmetricRoot.left.right = new TreeNode(3);
        asymmetricRoot.right.right = new TreeNode(3);

        Solution4 solution = new Solution4();

        // 测试对称二叉树
        boolean isSymmetric1 = solution.isSymmetric(symmetricRoot);
        System.out.println("对称二叉树测试结果: " + isSymmetric1);

        // 测试不对称二叉树
        boolean isSymmetric2 = solution.isSymmetric(asymmetricRoot);
        System.out.println("不对称二叉树测试结果: " + isSymmetric2);
    }
}

6、给定⼀个⼆叉树, 找到该树中两个指定节点的最近公共祖先。—题目链接

题目详解代码

package Demo2_26;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-26
 * Time:20:58
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
                          //解法一：


// 定义解决方案类
//class Solution5 {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (root == null) {
//            return null;
//        }
//        if (root == p || root == q) {
//            return root;
//        }
//        TreeNode leftT = lowestCommonAncestor(root.left, p, q);
//        TreeNode rightT = lowestCommonAncestor(root.right, p, q);
//        if (leftT != null && rightT != null) {
//            return root;
//        } else if (leftT != null) {
//            return leftT;
//        } else if (rightT != null) {
//            return rightT;
//        }
//        return null;
//    }

                   //解法二：
                   class Solution5 {
                       public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
                           if(root==null){
                               return false;
                           }
                           stack.push(root);
                           if(root==node){
                               return true;
                           }
                           boolean flg=getPath(root.left,node,stack);
                           if(flg){
                               return true;
                           }
                           flg=getPath(root.right,node,stack);
                           if(flg){
                               return true;
                           }
                           stack.pop();
                           return false;
                       }
                       public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
                           if(root==null){
                               return null;
                           }
                           Stack<TreeNode> stack1=new Stack<>();
                           Stack<TreeNode> stack2=new Stack<>();
                           getPath(root,p,stack1);
                           getPath(root,q,stack2);
                           int size1=stack1.size();
                           int size2=stack2.size();
                           int size=size1-size2;
                           if(size<0){
                               size=Math.abs(size);
                               while(size!=0){
                                   stack2.pop();
                                   size--;
                               }
                           }
                           else{
                               while(size!=0){
                                   stack1.pop();
                                   size--;
                               }
                           }
                           while(!stack1.isEmpty()&&!stack2.isEmpty()){
                               if(stack1.peek()==stack2.peek()){
                                   return stack1.pop();
                               }else{
                                   stack1.pop();
                                   stack2.pop();
                               }
                           }
                           return null;
                       }
                       
// 主类，用于测试
    public static void main(String[] args) {
        // 构建一个简单的二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        // 定义要查找的两个节点
        TreeNode p = root.left; // 节点 5
        TreeNode q = root.right; // 节点 1

        // 创建解决方案对象
        Solution5 solution = new Solution5();

        // 调用 lowestCommonAncestor 方法查找最近公共祖先
        TreeNode lca = solution.lowestCommonAncestor(root, p, q);

        // 输出结果
        if (lca != null) {
            System.out.println("最近公共祖先是: " + lca.val);
        } else {
            System.out.println("未找到最近公共祖先。");
        }
    }
}

7、⼆叉树创建字符串。—题目链接

题目详解代码

package Demo2_27;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-27
 * Time:17:14
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    // 构造函数，用于初始化节点的值
    TreeNode(int x) { val = x; }
}

class Solution {
    // 主方法，将二叉树转换为字符串
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root, stringBuilder);
        return stringBuilder.toString();
    }

    // 辅助方法，递归地将二叉树的节点添加到字符串构建器中
    public void tree2strChild(TreeNode root, StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        // 添加当前节点的值
        stringBuilder.append(root.val);
        if (root.left != null) {
            // 若左子节点不为空，添加左括号
            stringBuilder.append("(");
            // 递归处理左子树
            tree2strChild(root.left, stringBuilder);
            // 添加右括号
            stringBuilder.append(")");
        } else {
            if (root.right == null) {
                return;
            } else {
                // 左子节点为空但右子节点不为空，添加空括号
                stringBuilder.append("()");
            }
        }
        if (root.right != null) {
            // 若右子节点不为空，添加左括号
            stringBuilder.append("(");
            // 递归处理右子树
            tree2strChild(root.right, stringBuilder);
            // 添加右括号
            stringBuilder.append(")");
        } else {
            return;
        }
    }


    public static void main(String[] args) {
        // 创建示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);

        // 创建 Solution 类的实例
        Solution solution = new Solution();
        // 调用 tree2str 方法将二叉树转换为字符串
        String result = solution.tree2str(root);
        // 输出结果
        System.out.println(result);
    }
}

Java二叉树的题目就分享到这里了

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除

测试