二叉树恢复
今天刷了一些java基础相关的知识，类加载、线程并发，静态属性与成员加载时机等相关题目，未成体系，刷一道LeetCode作为今天的打卡
https://leetcode.cn/problems/recover-binary-search-tree/description/
题解：
package src;
import java.util.ArrayList;
import java.util.List;
//给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
class Solution {
public static void main(String[] args) {
// TreeNode root = new TreeNode(1);
// root.left = new TreeNode(3);
// root.left.right = new TreeNode(2);
TreeNode root = new TreeNode(3);
root.left = new TreeNode(1);
root.right = new TreeNode(4);
root.right.left = new TreeNode(2);
Solution solution = new Solution();
List<TreeNode> treeNodes = solution.recoverTree(root);
for (int i = 0; i < treeNodes.size(); i++) {
System.out.println(treeNodes.get(i).val);
}
}
public List<TreeNode> recoverTree(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
//正常二叉搜索树中序遍历应该是依次递增的，如果两个树交换位置后就会形成两个拐点，拐点会导致数据走势突然递减,
// 记录两次递减的坐标位置，交换坐标的值，
// 若只有一次递减，则交换第一次递减前后node的值
innerSearch(list, root);
int index = 0;
int firstIndex = -1;
int secondIndex = -1;
while (index < list.size() - 1) {
if (list.get(index).val <= list.get(index + 1).val) {
index++;
continue;
}
if (firstIndex == -1) {
firstIndex = index++;
continue;
}
secondIndex = index + 1;
break;
}
if (secondIndex == -1) {
secondIndex = firstIndex + 1;
}
int temp = list.get(firstIndex).val;
list.get(firstIndex).val = list.get(secondIndex).val;
list.get(secondIndex).val = temp;
return list;
}
private void innerSearch(List<TreeNode> list, TreeNode root) {
if (root == null) {
return;
}
innerSearch(list, root.left);
list.add(root);
innerSearch(list, root.right);
}
private static 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;
}
}
}
//还可以继续优化一下，在中序遍历的时候就比较记录下Node了，情人节，陪老婆去了
————————————————
版权声明：本文为CSDN博主「张野1994」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_24679971/article/details/129035299
