98. 验证二叉搜索树

解法一

二叉搜索树中序遍历是有序的,所以可以先全部遍历,在判断是否有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
List<Integer> list = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
isvailbst(root);
for(int i = 1;i < list.size(); i++) {
if(list.get(i) <= list.get(i - 1)) return false;
}
return true;
}
public void isvailbst(TreeNode root) {
if(root == null) return;
isvailbst(root.left);
list.add(root.val);
isvailbst(root.right);
}
}

解法二

上面的解法一其实可以看出是浪费了一些时间了的,其实可以直接在后一个值小于前一个值的时候就停下来的。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root != null) {
if(!isValidBST(root.left)) return false;
if(root.val <= pre) return false;
pre = root.val;
if(!isValidBST(root.right)) return false;
}
return true;
}
}

解法三

这种方法也很好,直接划个边界给给子树递归,判断是否出边界。不过注意的是,设置边界的最大值的时候,不能用Integer.MAX_VALUEInteger.MIN_VALUE,因为有样例正好是Integer.MAX_VALUEInteger.MIN_VALUE,所以只能取大一点的long。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean isValidBST(TreeNode root) {
return vailbst(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
public static boolean vailbst(TreeNode root,long min,long max) {
if(root == null) return true;
if(root.val <= min || root.val >= max) {
return false;
}
return vailbst(root.left,min,root.val) && vailbst(root.right,root.val,max);
}
}

100.相同的树

  1. 判断根节点的属性是否相同
  2. 递归判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}

101.对称二叉树

递归

  1. 判断根节点是否为空
  2. 判断左子树和右子树是否同时为空
  3. 判断左子树或右子树有一个是否为空
  4. 判断左子树的值是否和右子树的值相同
  5. 将左子树的左子树和右子树的右子树丢入递归判断,将左子树的右子树和右子树的左子树丢入递归判断,结果取并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return issymmetric(root.left, root.right);
}
public boolean issymmetric(TreeNode left,TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
return issymmetric(left.left,right.right)&&issymmetric(right.left,left.right);
}
}

迭代

使用双栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> left = new Stack<>();
Stack<TreeNode> right = new Stack<>();
left.push(root.left);
right.push(root.right);
while (!left.isEmpty() && !right.isEmpty()) {
TreeNode t1 = left.pop();
TreeNode t2 = right.pop();
if (t1 == null && t2 == null) {
continue;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
left.push(t1.left);
right.push(t2.right);
left.push(t1.right);
right.push(t2.left);
}
return true;
}
}

层次遍历

使用队列进行层次遍历,然后判断是否回文。

104.二叉树的最大深度

  1. 首先判断根节点是不是空,不是则值加一
  2. 递归判断左子树与右子树,取最大值
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int maxDepth(TreeNode root) {
int res = 0;
if (root == null) {
return res;
} else {
res ++;
}
return res + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}

优化之后:

1
2
3
4
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

107.二叉树的层次遍历II

从低向上层次遍历,其实就是先层次遍历然后反转就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
// 定义结果集
List<List<Integer>> res = new ArrayList<>();

public List<List<Integer>> levelOrderBottom(TreeNode root) {
levelorder(root,0);
// 反转list
List<List<Integer>> ans = new ArrayList<>();
for(int i = res.size()-1 ; i >= 0; i--) {
ans.add(res.get(i));
}
return ans;
}
public void levelorder(TreeNode node,int k) {
if (node != null) {
if (res.size() <= k) {
res.add(new ArrayList<Integer>());
}
res.get(k).add(node.val);
levelorder(node.left,k+1);
levelorder(node.right,k+1);
}
}
}

110.平衡二叉树

递归一

首先,判断左右两个子树的高度的绝对值不超过1,就要用到计算二叉树的最大深度了,递归获得深度,左右子树深度差的绝对值小于等于1就返回真,然后遍历左子树和右子树就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public boolean isBalanced(TreeNode root) {
// 判断是否为空,因为空了就直接停止递归了
// 为空就返回真,因为答案要与运算,返回真不会影响
if (root == null) {
return true;
}
// 判断是否符合平衡二叉树,用到否定条件
// 如果是用小于等于1返回真,那就没有false返回了,答案全是真
if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
return false;
}
// 遍历左子树和右子树取与
return isBalanced(root.left) && isBalanced(root.right);
}

// 最大深度遍历就直接用104题目的代码了。
public int maxDepth(TreeNode root) {
int res = 0;
if (root == null) {
return res;
} else {
res ++;
}
return res + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}

递归二

这个和上面算法差不多,这个算法是修改了最大深度的求法,不符和条件的就返回-1的深度,要是有-1深度返回代表不符合条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean isBalanced(TreeNode root) {
return maxDepth(root) >= 0;
}
public static int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftheight = maxDepth(root.left);
int rightheight = maxDepth(root.right);
// 判断左右子树是否平衡
if(leftheight >= 0 && rightheight >= 0 && Math.abs(leftheight - rightheight ) <= 1) {
return Math.max(leftheight,rightheight) + 1;
} else {
return -1;
}
}
}

111.二叉树的最小深度

求最小深度,就与求最大深度相反就好,只是不能让空子树参与计算,不然一直返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right !=null) {
return 1 + minDepth(root.right);
}
if (root.left != null && root.right == null) {
return 1 + minDepth(root.left);
}

return 1 + Math.min(minDepth(root.left),minDepth(root.right));

}
}

112.路径总和

这题是判断路径总和是否等于给定值,不能从下到上的计算节点值,因为情况多会无法相加,所以只能从上到下的相减,看是否等于0。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
// 如果是叶子节点,就直接计算是否符合
if (root.left == null && root.right == null) {
return sum - root.val == 0;
}
return hasPathSum(root.left,sum - root.val) || hasPathSum(root.right,sum - root.val);
}

}

589.N叉树的前序遍历

递归

  1. 判断root是否为空结点
  2. 将数据存入List
  3. 递归前序遍历各个结点

这道题难的就是结果的存储了,因为经常写的前序遍历都是直接输出结果的,存储的化就要全局的List了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> preorder(Node root) {
if (root == null) {
return res;
}
res.add(root.val);
for(Node node:root.children){
preorder(node);
}
return res;
}
}

非递归

  1. 先判断root是否为空结点
  2. 将root结点压入栈
  3. 当栈不为空,将栈中数据存入List,将当前结点的孩子压入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> preorder(Node root) {
List<Integer> res = new ArrayList<>();
Stack<Node> stack = new Stack();
if (root != null) {
return res;
}
stack.push(root);
Node node = null;
while (!stack.empty()) {
node = stack.pop();
res.add(node.val);
//注意压栈的顺序和出栈的顺序
for (int i = node.children.size() - 1; i >= 0; i++) {
stack.push(node.children.get(i));
}
}
return res;
}

897.递增顺序查找树

直接中序遍历然后把节点赋给结果子树的右子树就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
// head用来记录根节点,因为res要递归右子树
TreeNode head = new TreeNode();
TreeNode res = right;
public TreeNode increasingBST(TreeNode root) {
if (root == null) {
return null;
}
increasingBST(root.left);
// 将当前节点赋值给res的右子树,然后再进入右子树,左子树为空
res.right = root;
root.left=null;
res = res.right;
increasingBST(root.right);
return head.right;
}
}

从根到叶的二进制数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
int sum = 0;
public int sumRootToLeaf(TreeNode root) {
return sumroottoleaf(root,sum);
}
public int sumroottoleaf(TreeNode root,int sum) {
// 防止左右子树有一个是NULL的情况
if(root == null) {
return 0;
}
// 左移一位再加值
sum = sum*2 + root.val;
if(root.left == null && root.right == null){
return sum;
}
// 递归
return sumroottoleaf(root.left,sum) + sumroottoleaf(root.right,sum);
}
}

剑指 Offer 54. 二叉搜索树的第k大节点

暴力破解

我的第一想法就是直接全部遍历,排序然后找到第k大的节点,虽然效率不这么好,但是也是一种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
List<Integer> arr = new ArrayList<>();
public int kthLargest(TreeNode root, int k) {
largest(root);
Collections.sort(arr);
return arr.get(arr.size()-k);
}
public void largest(TreeNode root) {
if (root == null) {
return;
}
arr.add(root.val);
largest(root.left);
largest(root.right);
}
}

中序遍历

因为给的树是二叉搜索树,所以应该想到二叉搜索树的中序遍历就是有序的,所以可以省去排序的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
List<Integer> arr = new ArrayList<>();
public int kthLargest(TreeNode root, int k) {
largest(root);
return arr.get(arr.size()-k);
}
public void largest(TreeNode root) {
if (root == null) {
return;
}
largest(root.left);
arr.add(root.val);
largest(root.right);
}
}

直接寻找第k大的结点

中序遍历毕竟是要遍历整个树,所以效率也只是比暴力破解好了一点点而已,要想节约时间,那就只搜索到第K大的结点就停止就好了,所以就用到了二叉搜索树的性质。(若它的左子树不空,则左子树上所有结点的值均小于它的根结点根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。)通过中序遍历,找到第K个结点就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
int sum = 0,res = 0;
public int kthLargest(TreeNode root, int k) {
largest(root,k);
return res;
}
public void largest(TreeNode root,int k) {
if (root.right != null) {
largest(root.right,k);
}
sum++;
if(sum == k) {
res = root.val;
return;
}
if (root.left != null) {
largest(root.left,k);
}
}
}

面试题 04.03. 特定深度节点链表

首先就是这个链表的插入,如果使用尾插就需要在声明一个头节点的数组存储头节点,所以我用了头插法,不过要注意顺序,先将右子树的值插入链表再将左子树的值插入链表,这样就能符和题目的顺序了。还有就是链表数组的长度,第一个解法我就直接再加个函数求取树的最大深度了,套用第104题就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
int n = maxDepth(tree);
ListNode[] res = new ListNode[n];
listofdepth(tree,0,res);
return res;
}
public int maxDepth(TreeNode root) {
int res = 0;
if (root == null) {
return res;
} else {
res ++;
}
return res + Math.max(maxDepth(root.left), maxDepth(root.right));
}
public void listofdepth(TreeNode tree,int t,ListNode[] res) {
if(tree == null) {
return;
}
ListNode node = new ListNode();
node.val = tree.val;
node.next = null;
listofdepth(tree.right,t+1,res);
node.next = res[t];
res[t] = node;
listofdepth(tree.left,t+1,res);
}
}

这种解法速度还是很快的,只是消耗的内存有点多,可能题目就打算消耗多的内存。还有一种思路就是使用层次遍历,其实也差不多。也看了一下其他解法,不过很多的解法消耗的内存有点多,然后看到一些内存消耗低的解法,发现寻找深度的代码还可以优化,所以优化之后的代码效率高了很多,有些细节可能还能优化,不过感觉已经差不多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
int n = maxDepth(tree);
ListNode[] res = new ListNode[n];
listofdepth(tree,0,res);
return res;
}
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
public void listofdepth(TreeNode tree,int t,ListNode[] res) {
if(tree == null) {
return;
}
ListNode node = new ListNode();
node.val = tree.val;
node.next = null;
listofdepth(tree.right,t+1,res);
node.next = res[t];
res[t] = node;
listofdepth(tree.left,t+1,res);
}
}