二叉树---java---黑马

🕗 发布于 2024-09-22 13:29 java 开发语言

二叉树

遍历

遍历分两种

广度优先遍历

尽可能先访问距离根节点最近的节点，也称之为层序遍历。
在这里插入图片描述

深度优先遍历

对于二叉树，进一步分为三种

pre-order前序遍历，对于每一颗子树，先访问该节点，然后是左子树，最后是右子树；
in-order中序遍历，对于每一颗子树，先访问左子树，然后是该节点，最后是右子树；
post-order后序遍历，对于每一颗子树，先访问左子树，然后是右子树，最后是该节点；

使用递归方式实现

前序遍历

public class TreeNode{
    TreeNode left;
    int value;
    TreeNode right;
    
    public TreeNode() {
        
    }
    
    public TreeNode(TreeNode left, int value, TreeNode) {
        this.left = left;
        this.value = value;
        this.right = right;
    }
    
    @Override
    public String toString() {
        return String.valueOf(this.value);
    }
}

public class TreeTraversal{
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
            new TreeNode(new TreeNode(4, 2, null)), 
            1, 
            new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
    }
    
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.value + "\t");// 值
        preOrder(node.left);// 左
        preOrder(node.right);// 右
    }
    
    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        preOrder(node.left);// 左
        System.out.println(node.value + "\t");// 值
        preOrder(node.right);// 右
    }
    
    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        preOrder(node.left);// 左
        preOrder(node.right);// 右
        System.out.println(node.value + "\t");// 值
    }
    
}

非递归实现

前序遍历和中序遍历

public class TreeTraversal{
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
            new TreeNode(new TreeNode(4, 2, null)), 
            1, 
            new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
        Stack<Integer> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.println(curr.value);// 前序遍历
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                System.out.println(pop.value);// 中序遍历
                curr = pop.right;
            }
        }
    }
}

后序遍历

public class TreeTraversal{
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
            new TreeNode(new TreeNode(4, 2, null)), 
            1, 
            new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
        Stack<Integer> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == peek) {
                    pop = stack.pop();
                    System.out.println(pop.value);// 后序遍历
                } else {
                    curr = peek.right;
                }
            }
        }
    }
}

同时实现前序遍历、中序遍历和后序遍历

public class TreeTraversal{
    
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
            new TreeNode(new TreeNode(4, 2, null)), 
            1, 
            new TreeNode(new TreeNode(5, 3, new TreeNode(6))));
        Stack<Integer> stack = new Stack<>();
        TreeNode curr = root;// 当前节点
        TreeNode pop = null;// 最近一次弹栈节点
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                // 待处理左子树
                System.out.println(curr.value);// 前序遍历
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                // 无右子树
                if (peek.right == null) {
                    System.out.println(peek.value);// 中序遍历
                    pop = stack.pop();
                    System.out.println(pop.value);// 后序遍历
                } 
                // 右子树处理完成
                else if (peek.right == peek) {
                    pop = stack.pop();
                    System.out.println(pop.value);// 后序遍历
                } 
                // 待处理右子树
                else {
                    System.out.println(peek.value);// 中序遍历
                    curr = peek.right;
                }
            }
        }
    }
}

Leetcode

Leetcode101对称二叉树

public class Leetcode101{
    
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }
    
    public boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (right == null || left == null) {
            return false;
        }
        if (left.value != right.value) {
            return false;
        }
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

Leetcode104最大深度

方法一

使用递归

public class Leetcode104{
    
   public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int i = maxDepth(root.left);
        int j = maxDepth(root.right);
        return Math.max(i, j) + 1;
    }
}

方法二

使用后序遍历

public class Leetcode104{
    
   public int maxDepth(TreeNode root) {
        TreeNode curr = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pop = null;// 最近一次弹栈元素/节点
        int max = 0;// 栈的最大深度
        while(curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                if (stack.size() > max) {
                    max = stack.size();
                }
                curr = curr.next;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                } else {
                    curr = peek.right;
                }
            }
        }
    }
}

方法三

使用层序遍历

public class Leetcode104{
    
   public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();// 写在循环内，需要多次调用，所以写在循环外
            for(int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            depth++;
        }
        return depth;
    }
}

Leetcode111二叉树最小深度

方法一

public class Leetcode111{
    
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int d1 = minDepth(root.left);
        int d2 = minDepth(root.right);
        if (d1 == 0) {// 当左子树为空
            return d2 + 1;
        } 
        if (d2 == 0) {// 当右子树为空
            return d1 + 1;
        }
        return Math.min(d1, d2) + 1;
    }
}

方法二

使用层序遍历实现，找到第一个叶子节点，求得最小深度

public class Leetcode111{
    
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();// LinkedList可以作为双向链表、队列、栈
        queue.offer(root);
        int c1 = 1;
        int depth = 0;
        while (!queue.isEmpty()) {
            int c2 = 0;
            depth++;
            for(int i = 0; i < c1; i++) {
                TreeNode poll = queue.poll();
                if (poll.left == null && poll.right == null) {
                    return depth;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                    c2++;
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                    c2++;
                }
            }
            c1 = c2;
        }
        return depth;
    }
}

Leetcode226

二叉树反转

public class Leetcode226{
    public TreeNode invertTree(TreeNode root) {
        if (root == null ||(root.left == null && root.right == null)) {
            return root;
        }
        fn(root);
        return root;
    }
    
    public void fn(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        fn(node.left);
        fn(node.right);
    }
}

后缀表达式构建二叉树

中缀表达式(2 - 1) * 3
后缀表达式/逆波兰表达式21-3*
    
    表达树
    *
   / \
  -   3
 / \
2   1

public class ExpressionTree{
    
    public TreeNode constructExpressionTree (String[] tokens){
        Stack<TreeNode> stack = new Stack<>();
        for(String t : tokens) {
            switch (t) {
                case "+", "-", "*", "/" -> {// 运算符
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode parent = new TreeNode(t);
                    parent.left = left;
                    parent.right = right;
                    stack.push(parent);
                }
                default -> {// 数字
                    stack.push(new TreeNode(t));
                }    
            }
        }
        return stack.peek();
    }
}

Leetcode105

根据前序遍历和中序遍历，得到二叉树

public class Leetcode105{
    public TreeNode buildTree(int[] preOrder, int inOrder) {
        if (preOrder.length == 0) {
            return null;
        }
        // 创建根节点
        int rootValue = preOrder[0];
        TreeNode root = new TreeNode(rootValue);
        for(int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
                
                int[] preLeft = preLeftArrays.copyOfRange(preOrder, 1, i + 1);
                int[] preRight = Arrays.copyOfRange(preOrder, i + 1, preOrder.length);
                
                root.left = buildTree(preLeft, inLeft);
                root.right = buildTree(preRight, inRight);
                break;
            }
        }
        return root;
    }
}

Leetcode106

根据中序遍历和后序遍历得到二叉树

public class Leetcode106{
    public TreeNode buildTree(int[] inOrder, int postOrder) {
        if (postOrder.length == 0) {
            return null;
        }
        // 创建根节点
        int rootValue = postOrder[postOrder.length - 1];
        TreeNode root = new TreeNode(rootValue);
        for(int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
                
                int[] postLeft = preLeftArrays.copyOfRange(preOrder, 0, i);
                int[] postRight = Arrays.copyOfRange(preOrder, i, preOrder.length - 1);
                
                root.left = buildTree(inLef, tpostLeft);
                root.right = buildTree(inRight, postRight);
                break;
            }
        }
        return root;
    }
}

            int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);
            
            int[] postLeft = preLeftArrays.copyOfRange(preOrder, 0, i);
            int[] postRight = Arrays.copyOfRange(preOrder, i, preOrder.length - 1);
            
            root.left = buildTree(inLef, tpostLeft);
            root.right = buildTree(inRight, postRight);
            break;
        }
    }
    return root;
}

}

原文地址：https://blog.csdn.net/weixin_49326024/article/details/142433016

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：动手学深度学习（李沐）PyTorch 第 2 章预备知识
下一篇：【H2O2|全栈】关于CSS（5）如何制作一个搜索网页的首页？

MySQL和SQL的区别简单了解和分析使用以及个人总结
数据库
阅读更多2024-09-24
前端常用的设计模式
工厂模式提供了一种创建对象的方式，而无需指定要创建的具体类。通过使用工厂模式，可以将对象的创建逻辑封装在一个工厂类中，而不是在客户端代码中直接实例化对象，这样可以提高代码的可维护性和可扩展性。每次增加
阅读更多2024-09-24
使用git命令
如果合并时出现冲突，需要手动编辑冲突的文件，解决后再次执行。
阅读更多2024-09-24
探索C语言与Linux编程：获取当前用户ID与进程ID
在操作系统与编程语言的交汇点，Linux作为开源操作系统的典范，为开发者提供了丰富的系统调用接口，使得我们可以深入操作系统内核，执行各种底层操作。C语言，作为系统编程的首选语言，其强大的功能和灵活性使
阅读更多2024-09-24
YOLO V10简单使用
官方GitHub地址：https://github.com/THU-MIG/yolov10。
阅读更多2024-09-24
字母与符号检测系统源码分享
数据集信息展示在本研究中，我们使用了名为“Project 2”的数据集，以改进YOLOv8的字母与符号检测系统。该数据集的设计旨在提供丰富的样本，以支持模型在多种条件下的训练和验证，确保其在实际应用中
阅读更多2024-09-24
Python中的“打开与关闭文件”：从入门到精通
在日常生活中，我们经常会遇到需要读取或保存信息的情况，比如记录笔记、保存配置信息或者处理大量的数据文件等。对于程序员来说，如何高效、安全地管理这些信息显得尤为重要。Python中的文件操作功能强大且易
阅读更多2024-09-24
解决element plus报错ResizeObserver loop completed with undelivered notifications.
具体原理暂时还不知道，记录一下，后面了解清楚，再补充吧。加入代码，重新编译，问题解决~~在使用动态数据切换渲染。
阅读更多2024-09-24
CF1494F Delete The Edges 题解
CF1494F Delete The Edges 题解
阅读更多2024-09-24
论文阅读与分析：Few-Shot Graph Learning for Molecular Property Prediction
图神经网络最近的成功显着促进了分子特性预测，推进了药物发现等活动。现有的深度神经网络方法通常需要每个属性都需要大量的训练数据集，在实验数据有限的情况下（特别是新的分子属性）会损害其性能，这在现实情
阅读更多2024-09-24