树的大部分问题都可以通过递归解决,即求一个树的某个值可以转化为求左子树/右子树的值
二叉树最大深度就是max(左子树的最大深度,右子树的最大深度) + 1(根节点)
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return left < right ? right + 1: left+1;
}
二叉搜索树是自左向右的有序树,可以通过中序遍历,然后判断中序遍历的结果是否有序
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
List<Integer> values = new ArrayList<Integer>();
inOrder(root, values);
for (int i = 0; i < values.size() - 1; i++) {
if (values.get(i) >= values.get(i + 1)) {
return false;
}
}
return true;
}
// 中序遍历
public void inOrder(TreeNode root, List<Integer> values) {
if (root == null) {
return;
}
inOrder(root.left, values);
values.add(root.val);
inOrder(root.right, values);
}
对称二叉树就是判断左右子树对称,递归方法即可
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isNodeSymmetric(root.right, root.left);
}
private boolean isNodeSymmetric(TreeNode right, TreeNode left) {
if (right == null && left == null) {
return true;
}
if (right == null || left == null) {
return false;
}
boolean result = right.val == left.val && isNodeSymmetric(right.right, left.left) &&
isNodeSymmetric(right.left, left.right);
return result;
}
二叉树的层次遍历需要利用额外数据结构队列,将上一层的节点从左到右放在队列中,下一层的节点值,就是通过上一层的节点的左右节点得到。
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
LinkedList<TreeNode> nextQueue = new LinkedList<TreeNode>();
queue.add(root);
List<Integer> level0 = new ArrayList<Integer>();
level0.add(root.val);
result.add(level0);
if (root.left != null) {
nextQueue.add(root.left);
}
if (root.right != null) {
nextQueue.add(root.right);
}
while (!nextQueue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
queue = (LinkedList<TreeNode>) nextQueue.clone();
nextQueue.clear();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
nextQueue.add(node.left);
}
if (node.right != null) {
nextQueue.add(node.right);
}
}
if (!level.isEmpty()) {
result.add(level);
}
}
return result;
}
上面这个解法有问题,queue其实没有用,还进行了队列的深拷贝,空间复杂度高,并且花费的时间比较久,
if (root == null) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
List<Integer> level0 = new ArrayList<Integer>();
level0.add(root.val);
result.add(level0);
if (root.left != null) {
queue.add(root.left);
}
if (root.right != null) {
queue.add(root.right);
}
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int count = queue.size();
while (count-- > 0) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
if (!level.isEmpty()) {
result.add(level);
}
}
return result;
二叉搜索树本身就是有序的,所以将有序数组转换为二叉搜索树,就是按照左根右的顺序构建树,根节点就是中间的值,使用递归来解决
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return generateSortedArray(nums, 0, nums.length -1);
}
private TreeNode generateSortedArray(int[] nums , int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end)/2;
TreeNode head = new TreeNode(nums[mid]);
head.left = generateSortedArray(nums, start, mid -1);
head.right = generateSortedArray(nums, mid+1,end);
return head;
}