第3章 二叉树问题(找到搜索二叉树中的两个错误节点)
2021/8/24 23:39:05
本文主要是介绍第3章 二叉树问题(找到搜索二叉树中的两个错误节点),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【题目】
一颗二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这个二叉树不再是搜索二叉树,请找到这两个错误节点并返回。
package zyc.binaryTree; import java.util.Stack; public class P137_getTwoErrorNode { public static Node[] getTwoErrorNode(Node node) { Node[] errors = new Node[2]; if (node == null) { return errors; } // 搜索二叉树采用 中序遍历 Node pre = null; Stack<Node> nodeStack = new Stack<>(); while (node != null || !nodeStack.isEmpty()) { if (node != null) { nodeStack.add(node); node = node.left; } else { Node cur = nodeStack.pop(); if (pre != null && pre.value > cur.value) { // 第一个错误节点是 首次降序的较大节点 errors[0] = errors[0] == null ? pre : errors[0]; // 第二个错误节点是 最后一次降序的较小节点 errors[1] = cur; } pre = cur; node = cur.right; } } return errors; } public static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } }
这篇关于第3章 二叉树问题(找到搜索二叉树中的两个错误节点)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署