邵阳网站建设网站,网站建设调查表,农村自建房设计网站,发新闻稿平台提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣109. 有序链表转换二叉搜索树二、力扣1382. 将二叉搜索树变平衡 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式#xff0c;这道题需要用到… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣109. 有序链表转换二叉搜索树二、力扣1382. 将二叉搜索树变平衡 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式这道题需要用到「分解问题」的思维模式。
一、力扣109. 有序链表转换二叉搜索树
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public TreeNode sortedListToBST(ListNode head) {ListInteger list new ArrayList();ListNode p head;while(p ! null){list.add(p.val);p p.next;}return fun(list,0,list.size()-1);}public TreeNode fun(ListInteger list, int low,int high){if(low high){return null;}int mid (lowhigh)/2;TreeNode cur new TreeNode(list.get(mid));cur.left fun(list,low,mid-1);cur.right fun(list,mid1,high);return cur;}
}二、力扣1382. 将二叉搜索树变平衡
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {ListInteger list new ArrayList();public TreeNode balanceBST(TreeNode root) {traverse(root);return fun(0,list.size()-1);}public TreeNode fun(int low, int high){if(low high){return null;}int mid (lowhigh)/2;TreeNode cur new TreeNode(list.get(mid));cur.left fun(low,mid-1);cur.right fun(mid1,high);return cur;}public void traverse(TreeNode root){if(root null){return;}traverse(root.left);list.add(root.val);traverse(root.right);}
}
