《程序员代码面试指南》第一章 栈和队列 构造数组的MaxTree
2024-09-01 11:00:56
题目
给出一个无重复元素的数组，构造此数组的MaxTree，
java代码
/**
* @Description: 构造数组的MaxTree
* @Author: lizhouwei
* @CreateDate: 2018/4/5 22:16
* @Modify by:
* @ModifyDate:
*/
public class Chapter1_8 {
public Node getMaxTree(int[] arr) {
if (arr == null) {
return null;
}
int length = arr.length;
Node[] nodes = new Node[length];
//初始化Node数组
for (int i = 0; i < length; i++) {
nodes[i] = new Node(arr[i]);
}
//存放当前节点往左 第一个大于当前节点的节点
Map<Node, Node> leftMap = new HashMap<Node, Node>();
//存放当前节点往右 第一个大于当前节点的节点
Map<Node, Node> rightMap = new HashMap<Node, Node>();
//存放遍历到节点
Stack<Node> stack = new Stack<Node>();
for (int i = 0; i < length; i++) {
//关键地方，判断栈顶元素的值是否小于当前元素的值，如果小于则在map中记录栈顶元素的往左数第一个元素
while (!stack.isEmpty() && stack.peek().value < nodes[i].value) {
popStackToMap(stack, leftMap);
}
//存放当前元素，前提保证栈中没有比小的元素
stack.push(nodes[i]);
}
//如果栈中还有元素，则循环获取栈中元素的往左数第一个大于他的元素
while (!stack.isEmpty()) {
popStackToMap(stack, leftMap);
}
for (int i = length - 1; i >= 0; i--) {
//关键地方，判断栈顶元素的值是否小于当前元素的值，如果小于则在map中记录栈顶元素的往右数第一个元素
while (!stack.isEmpty() && stack.peek().value < nodes[i].value) {
popStackToMap(stack, rightMap);
}
//存放当前元素，前提保证栈中没有比小的元素
stack.push(nodes[i]);
}
//如果栈中还有元素，则循环获取栈中元素的往右数第一个大于他的元素
while (!stack.isEmpty()) {
popStackToMap(stack, rightMap);
}
//再将 每个元素 左右 最大的元找见后，开始构造MaxTree
Node head = null;
for (int i = 0; i < length; i++) {
Node node = nodes[i];
Node leftNode = leftMap.get(node);
Node rightNode = rightMap.get(node);
//左右最大的元素都为空，则此元素是数组中最大，作为根节点
if (leftNode == null && rightNode == null) {
head = node;
} else if (leftNode == null) {
if (rightNode.left == null) {
rightNode.left = node;
} else {
rightNode.right = node;
}
} else if (rightNode == null) {
if (leftNode.left == null) {
leftNode.left = node;
} else {
leftNode.right = node;
}
} else {
Node parent = leftNode.value < rightNode.value ? leftNode : rightNode;
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
}
return head;
}
public void popStackToMap(Stack<Node> stack, Map<Node, Node> map) {
Node node = stack.pop();
if (stack.isEmpty()) {
map.put(node, null);
} else {
map.put(node, stack.peek());
}
}
//简单的用递归中序遍历一下生成的MaxTree
public void recInOrder(Node head) {
if (head == null) {
return;
}
recInOrder(head.left);
System.out.print(head.value + " ");
recInOrder(head.right);
}
//测试
public static void main(String[] args) {
Chapter1_8 chapter = new Chapter1_8();
int[] arr = {3, 4, 5, 1, 2};
Node head = chapter.getMaxTree(arr);
chapter.recInOrder(head);
}
}
class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
最新文章
- Traveling in Blade & Soul
- C++模板机制总结
- 霸气！Nginx 中缓存静态文件秘籍
- POJ 2080
- ListView的item选中效果
- 鼠标到哪tl到哪
- CSS 高级
- eclipse中配置免安装tomcat7
- U盘装centos7系统过程
- (转)C++中返回对象的情形及RVO
- angularjs ng-class
- MySQL分区表与合并表
- 第一届“百度杯”信息安全攻防总决赛_Upload
- [C++]动态规划系列之币值最大化
- C++Primer笔记——文本查询程序（原创，未使用类）
- linux令普通用户拥有root权限
- 20155312 2016-2017-2 《Java程序设计》第十周学习总结
- Java 范例 - 线程
- linux常用命令：du 命令
- js阻止冒泡和默认事件（默认行为）详解- jquery DefaultPrevented 函数