Day56 | 99. 恢复二叉搜索树、103. 二叉树的锯齿形层序遍历、109. 有序链表转换二叉搜索树、113. 路径总和 II

99. 恢复二叉搜索树

题目链接：99. 恢复二叉搜索树 - 力扣（LeetCode）

题目难度：中等

代码：

class Solution {public void recoverTree(TreeNode root) {List<TreeNode> list=new ArrayList<>();dfs(root,list);TreeNode x=null;TreeNode y=null;for(int i=0;i<list.size()-1;i++){if(list.get(i).val>list.get(i+1).val){y=list.get(i+1);if(x==null){x=list.get(i);}}}if(x!=null&&y!=null){int tmp=x.val;x.val=y.val;y.val=tmp;}}public void dfs(TreeNode node,List<TreeNode> list){if(node==null) return;dfs(node.left,list);list.add(node);dfs(node.right,list);}
}

103. 二叉树的锯齿形层序遍历

题目链接：103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

题目难度：中等

代码：

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {Queue<TreeNode> queue=new LinkedList<>();List<List<Integer>> res=new ArrayList<>();if(root!=null) queue.add(root);while(!queue.isEmpty()){LinkedList<Integer> tmp=new LinkedList<>();for(int i=queue.size();i>0;i--){TreeNode node=queue.poll();if(res.size()%2==0) tmp.addLast(node.val);else tmp.addFirst(node.val);if(node.left!=null) queue.add(node.left);if(node.right!=null) queue.add(node.right);}res.add(tmp);}return res;}
}

109. 有序链表转换二叉搜索树

题目链接：109. 有序链表转换二叉搜索树 - 力扣（LeetCode）

题目难度：中等

代码：

class Solution {public TreeNode sortedListToBST(ListNode head) {return buildTree(head, null);}public TreeNode buildTree(ListNode left, ListNode right) {if (left == right) {return null;}ListNode mid = getMedian(left, right);TreeNode root = new TreeNode(mid.val);root.left = buildTree(left, mid);root.right = buildTree(mid.next, right);return root;}public ListNode getMedian(ListNode left, ListNode right) {ListNode fast = left;ListNode slow = left;while (fast != right && fast.next != right) {fast = fast.next;fast = fast.next;slow = slow.next;}return slow;}
}

113. 路径总和 II

题目链接：113. 路径总和 II - 力扣（LeetCode）

题目难度：中等

代码：

class Solution {LinkedList<List<Integer>> res = new LinkedList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {recur(root, targetSum);return res;}public void recur(TreeNode root, int tar) {if (root == null) return;path.add(root.val);tar -= root.val;if (tar == 0 && root.left == null && root.right == null)res.add(new LinkedList<Integer>(path));recur(root.left, tar);recur(root.right, tar);path.removeLast();}
}