力扣labuladong——一刷day72

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「分解问题」的思维模式。

一、力扣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) {List<Integer> 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(List<Integer> list, int low,int high){if(low > high){return null;}int mid = (low+high)/2;TreeNode cur = new TreeNode(list.get(mid));cur.left = fun(list,low,mid-1);cur.right = fun(list,mid+1,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 {List<Integer> 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 = (low+high)/2;TreeNode cur = new TreeNode(list.get(mid));cur.left = fun(low,mid-1);cur.right = fun(mid+1,high);return cur;}public void traverse(TreeNode root){if(root == null){return;}traverse(root.left);list.add(root.val);traverse(root.right);}
}