1、二叉树的层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//存放结果
List<List<Integer>> levels = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null ) return levels;
solve(root,0);
return levels;
}
//处理函数
public void solve (TreeNode node,int level){
//新建当前层
if(levels.size() == level) levels.add(new ArrayList<Integer>());
//插入值
levels.get(level).add(node.val);
//递归处理其子节点
if(node.left != null) solve(node.left, level+1);
if(node.right != null) solve(node.right, level+1);
}
}
2、二叉树的最小深度
思路：
很多人写出的代码都不符合 1,2 这个测试用例，是因为没搞清楚题意
题目中说明:叶子节点是指没有子节点的节点，这句话的意思是 1 不是叶子节点
题目问的是到叶子节点的最短距离，所以所有返回结果为 1 当然不是这个结果
另外这道题的关键是搞清楚递归结束条件
叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
- 当 root 节点左右孩子都为空时，返回 1
- 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
- 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int m1 = minDepth(root.left);
int m2 = minDepth(root.right);
//1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
//2.如果都不为空，返回较小深度+1
return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
}
}
3、验证二叉搜索树
思路：
通过中序遍历将所有的节点值存到一个数组里，然后再来判断这个数组是不是有序的，代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) return true;
orderBST(root, list);
for (int i = 0; i < list.size() - 1; i++) {
if (list.get(i) >= list.get(i + 1)) return false;
}
return true;
}
/**
* 中序遍历
*/
private void orderBST(TreeNode root, List<Integer> list) {
if (root == null) return;
orderBST(root.left, list);
list.add(root.val);
orderBST(root.right, list);
}
}
4、有序序列转换二叉平衡搜索树
题目描述：
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/
-3 9
/ /
-10 5
思路：
这题比较简单。高度平衡二叉搜索树，那么从中间开始构建树即可。
代码如下
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode solve(int[] nums ,int left ,int right){
if(left > right) return null;
int p = (left + right) >>> 1; //取中间值
//来左右孩子看一看呀
TreeNode root = new TreeNode(nums[p]);
root.left = solve(nums,left, p - 1);
root.right = solve(nums,p + 1, right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
return solve(nums,0,nums.length - 1); //目标解决函数
}
}
