二叉树算法一

108. 将有序数组转换为二叉搜索树 - 力扣LeetCode有序数组从中间位置递归两侧生成树就是搜索树。class Solution { public TreeNode sortedArrayToBST(int[] nums) { return dfs(nums, 0, nums.length -1); } // nums在leftright闭区间上生成树 TreeNode dfs(int[]nums, int left, int right){ if(left right){ return null; } int mid left (right-left)/2; TreeNode root new TreeNode(nums[mid]); root.left dfs(nums, left, mid-1); root.right dfs(nums, mid1, right); return root; } }101. 对称二叉树 - 力扣LeetCode比较两颗子树是否为对称class Solution { public boolean isSymmetric(TreeNode root) { if(root null){ return true; } return dfs(root.left, root.right); } boolean dfs(TreeNode l , TreeNode r){ if(l null r null){ return true; } if(l null || r null){ return false; } if(l.val ! r.val){ return false; } return dfs(l.left, r.right) dfs(l.right, r.left); } }98. 验证二叉搜索树 - 力扣LeetCode树的值都在l,r范围内并且是bstclass Solution { public boolean isValidBST(TreeNode root) { return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE); } // 树的值在(l,r)里 boolean dfs(TreeNode root, long left, long right){ if(root null){ return true; } long x root.val; return dfs(root.left, left, x) dfs(root.right, x, right) left x x right; } }230. 二叉搜索树中第 K 小的元素 - 力扣LeetCode找中序遍历的第k个元素class Solution { int res; int k; public int kthSmallest(TreeNode root, int k) { this.k k; dfs(root); return res; } void dfs(TreeNode root){ if(root null){ return; } dfs(root.left); if(k0)return; if(--k0){ res root.val; return;}; dfs(root.right); } }199. 二叉树的右视图 - 力扣LeetCode层序遍历应用class Solution { public ListInteger rightSideView(TreeNode root) { ListInteger res new ArrayList(); if(root null) return res; DequeTreeNode nodes new LinkedList(); nodes.add(root); while(!nodes.isEmpty()){ int n nodes.size(); res.add(nodes.getLast().val); for(int i 0; i n;i){ TreeNode cur nodes.poll(); if(cur.left ! null){ nodes.offer(cur.left); } if(cur.right ! null){ nodes.offer(cur.right); } } } return res; } }