12380举报网站建设情况,用rem做移动网站,润和软件是外包公司吗,wordpress 关闭ajax想要精通算法和SQL的成长之路 - 恢复二叉搜索树和有序链表转换二叉搜索树 前言一. 恢复二叉搜索树二. 有序链表转换二叉搜索树 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 恢复二叉搜索树
原题链接
首先#xff0c;一个正常地二叉搜索树在中序遍历下#xff0c;遍历… 想要精通算法和SQL的成长之路 - 恢复二叉搜索树和有序链表转换二叉搜索树 前言一. 恢复二叉搜索树二. 有序链表转换二叉搜索树 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 恢复二叉搜索树
原题链接
首先一个正常地二叉搜索树在中序遍历下遍历的元素一定是单调递增的。而题目中提醒道正好有两个节点被互换了。那么以下面的递增序列为例
[1,2,3,4,5,6,7]。被替换后[1,2,6,4,5,3,7]它一定满足一个特性存在两个地方满足递减的情况。第一个问题点6,4。这里我们需要找到第一个下一个元素比当前元素小的我们取当前元素。取前者。第二个问题点5,3在找到第一个问题点的前提下再找下一个元素比当前元素小的我们取后者。最后两个问题节点值互换即可不可以节点互换一定是值互换
TreeNode firstNode, secondNode, preNode new TreeNode(Integer.MIN_VALUE);public void recoverTree(TreeNode root) {inOrderReadTree(root);int tmp firstNode.val;firstNode.val secondNode.val;secondNode.val tmp;
}public void inOrderReadTree(TreeNode root) {if (root null) {return;}// 左中右的顺序遍历inOrderReadTree(root.left);// 找到第一个开始递减的元素if (firstNode null preNode.val root.val) {firstNode preNode;// 取前者}// 找到第一个节点的前提下找到第二个开始递减的元素if (firstNode ! null preNode.val root.val) {secondNode root;// 取后者}preNode root;inOrderReadTree(root.right);
}二. 有序链表转换二叉搜索树
原题链接 首先一点题目的入参是一个链表对于链表而言不好操作我们可以先把他转为数组
// 构建成数组入参是head
ArrayListInteger tmp new ArrayList();
while (head ! null) {tmp.add(head.val);head head.next;
}
int[] arr new int[tmp.size()];
for (int i 0; i arr.length; i) {arr[i] tmp.get(i);
}其次既然要高度平衡那么这个题目而言我们必定是针对转化后的数组不断地以中间节点为根节点向左右两侧构建树。
那么就是一个很简单的分治递归法
public TreeNode buildTree(int left, int right, int[] arr) {if (left right) {return null;}// 中间节点下标int mid (left right) 1;TreeNode root new TreeNode(arr[mid]);root.left buildTree(left, mid - 1, arr);root.right buildTree(mid 1, right, arr);return root;
}完整代码如下
public TreeNode sortedListToBST(ListNode head) {// 构建成数组ArrayListInteger tmp new ArrayList();while (head ! null) {tmp.add(head.val);head head.next;}int[] arr new int[tmp.size()];for (int i 0; i arr.length; i) {arr[i] tmp.get(i);}TreeNode treeNode buildTree(0, arr.length - 1, arr);return treeNode;
}public TreeNode buildTree(int left, int right, int[] arr) {if (left right) {return null;}// 中间节点下标int mid (left right) 1;TreeNode root new TreeNode(arr[mid]);root.left buildTree(left, mid - 1, arr);root.right buildTree(mid 1, right, arr);return root;
}
