当前位置： 首页 > article >正文

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

article 2024/9/24 3:30:49

二叉树

遍历

遍历分两种

广度优先遍历

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

深度优先遍历

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

  1. pre-order前序遍历，对于每一颗子树，先访问该节点，然后是左子树，最后是右子树；
  2. in-order中序遍历，对于每一颗子树，先访问左子树，然后是该节点，最后是右子树；
  3. 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;
}

}


http://www.kler.cn/news/316950.html

相关文章：

  • 吴恩达深度学习笔记：卷积神经网络（Foundations of Convolutional Neural Networks）2.1-2.2
  • 【IPV6从入门到起飞】5-5 IPV6+Home Assistant(HACS商店安装)docker版本安装
  • Leetcode3289. 数字小镇中的捣蛋鬼
  • vue中高德地图使用 Marker 标点 - 标点数据快到 1000 时页面卡顿问题解决（已解决 - 多方面原因）+ 海量点功能实现解决
  • 南昌大学-计算机科学与技术专业-预推免-专业课（408）复试面试准备
  • 通信工程学习：什么是MANO管理编排
  • 蓝桥杯嵌入式的学习总结
  • 18 基于51单片机的心率体温监测报警系统(包括程序、仿真、原理图、流程图)
  • helm安装promethues
  • MySQL的缓存策略
  • 数据结构二
  • 影刀RPA实战：网页爬虫之携程酒店数据
  • 文件（打开关闭读写） C语言
  • 面向对象程序设计——mapの简析
  • kettle从入门到精通 第八十七课 ETL之kettle kettle文件上传
  • DevExpress中文教程：如何将WinForms数据网格连接到ASP. NET Core WebAPI服务？
  • 笔记9.18
  • C++速通LeetCode中等第1题-字母异位词分组
  • 在vue中:style 的几种使用方式
  • 【Elasticsearch系列五】Java API
  • Day30_0.1基础学习MATLAB学习小技巧总结（30）——优化工具箱及
  • prime1靶机渗透 (信息收集 内核提权)
  • H5白色大方图形ui设计公司网站HTML模板源码
  • DSP学习00-F28379D学习准备(了解一个工程的构成)
  • python mysql pymysql 数据库操作，常用脚本，个人小工具
  • 通过 LabVIEW 正则表达式读取数值（整数或小数）
  • Java基础尚硅谷85-面向对象特征一：封装性
  • Java中的事件（动作监听-ActionListener）
  • 如何使用ssm实现企业文档管理系统+vue
  • OpenHarmony（鸿蒙南向开发）——小型系统内核（LiteOS-A）【Perf调测】