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_VALUE
和Integer.MIN_VALUE
,因为有样例正好是Integer.MAX_VALUE
和Integer.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 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 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 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<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; } if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) { return false; } return isBalanced(root.left) && isBalanced(root.right); } 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叉树的前序遍历
递归
- 判断root是否为空结点
- 将数据存入List
- 递归前序遍历各个结点
这道题难的就是结果的存储了,因为经常写的前序遍历都是直接输出结果的,存储的化就要全局的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; } }
|
非递归
- 先判断root是否为空结点
- 将root结点压入栈
- 当栈不为空,将栈中数据存入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 { TreeNode head = new TreeNode(); TreeNode res = right; public TreeNode increasingBST(TreeNode root) { if (root == null) { return null; } increasingBST(root.left); 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) { 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); } }
|