94. 二叉树的中序遍历
递归
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) return res;
fnc(root);
return res;
}
public void fnc(TreeNode node) {
if (node == null) return;
fnc(node.left);
res.add(node.val);
fnc(node.right);
}
}迭代
迭代会麻烦一点，主要先记住中序遍历的特点，先遍历左子树，在遍历当前节点，在遍历右子树。
所以当该节点有左子树的时候就先进入到左边。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<>();
while(!stack.isEmpty() || root != null) {
// 一直寻找左节点
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// 处理左子树的当前节点，进入右子树
res.add(root.val);
root = root.right;
}
return res;
}
}98. 验证二叉搜索树
解法一
二叉搜索树中序遍历是有序的，所以可以先全部遍历，在判断是否有序。
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);
}
}解法二
上面的解法一其实可以看出是浪费了一些时间了的，其实可以直接在后一个值小于前一个值的时候就停下来的。
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。
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.相同的树
相同的树，首先要判断当前节点是否相同。不相同直接返回false。
然后递归判断两棵树的左子树和右子树，判断一下他们的左子树是否相同和右子树是否相同即可。
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.对称二叉树
递归
- 判断当前节点是否是一样的
- 将左子树的左子树和右子树的右子树丢入递归判断，将左子树的右子树和右子树的左子树丢入递归判断，结果取并
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);
}
}迭代
使用双栈。
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;
}
}层次遍历
使用队列进行层次遍历，然后判断是否回文。
102. 二叉树的层序遍历
递归解法
主要是判断一下是在哪一层，然后分层处理就可以了。
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
levelorder(root,0);
return res;
}
public void levelorder(TreeNode node,int k) {
if (node == null) return;
// 没有当前层
if (res.size() <= k) {
res.add(new ArrayList<Integer>());
}
// 将节点放入k层的List中
res.get(k).add(node.val);
// 递归处理
levelorder(node.left,k+1);
levelorder(node.right,k+1);
}
}迭代解法
二叉树的层序遍历的迭代可以借组队列来进行存储节点。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> deque = new LinkedList<>();
deque.offer(root);
while (!deque.isEmpty()) {
// 统计当前层的节点个数
int count = deque.size();
List<Integer> list = new ArrayList<>(count);
while (count-- > 0) {
TreeNode node = deque.poll();
list.add(node.val);
// 先加入左节点在加入右节点，z
if (node.left != null) deque.offer(node.left);
if (node.right != null) deque.offer(node.right);
}
res.add(list);
}
return res;
}
}104.二叉树的最大深度
- 首先判断根节点是不是空，不是则值加一
- 递归判断左子树与右子树，取最大值
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));
}
}优化之后：
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}105.从前序与中序遍历序列构造二叉树
假设根的前序遍历的在中序遍历中的位置为K，那么在中序遍历中，1到K-1都是该根的左子树，K+1到最后是该根的右子树。
class Solution {
int pre = 0;
int ino = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,inorder,Integer.MAX_VALUE + 1);
}
// stop表示当前子树根的值，中序遍历到了该值，就表示左子树已经搭建好了
public TreeNode build(int[] preorder,int[] inorder, long stop) {
if (pre == preorder.length) return null;
if (inorder[ino] == stop) {
ino++;
return null;
}
int val = preorder[pre++];
TreeNode root = new TreeNode(val);
root.left = build(preorder,inorder,val);
root.right = build(preorder,inorder,stop);
return root;
}
}106.从中序与后序遍历序列构造二叉树
与上一题差不多，只是有一点点不一样而已。
class Solution {
int ino = 0;
int pos = 0;
public TreeNode buildTree(int[] inorder, int[] postorder) {
pos = postorder.length - 1;
ino = inorder.length - 1;
return build(inorder,postorder,Integer.MIN_VALUE - 1);
}
public TreeNode build(int[] inorder, int[] postorder,long stop) {
if (pos == -1) return null;
if (inorder[ino] == stop) {
ino--;
return null;
}
int val = postorder[pos--];
TreeNode root = new TreeNode(val);
root.right = build(inorder,postorder,val);
root.left = build(inorder,postorder,stop);
return root;
}
}.
107.二叉树的层次遍历II
从低向上层次遍历，其实就是先层次遍历然后反转就好了。
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就返回真，然后遍历左子树和右子树就好了。
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深度返回代表不符合条件。
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。
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。
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);
}
}230.二叉搜索树中第K小的元素
这题就是根据二叉搜索树的特性，中序遍历会是从小到大，然后找到第K个就好了。
class Solution {
int res = 0;
int rank = 0;
public int kthSmallest(TreeNode root, int k) {
small(root,k);
return res;
}
public void small(TreeNode root,int k) {
if (root == null) return;
small(root.left,k);
rank++;
if (k == rank) {
res = root.val;
return;
}
small(root.right,k);
}
}上面的方法是最暴力的解法，还可以进行优化。根据二叉搜索树的左子树会比根节点小，右子树会比根节点大，就可以找到第K小的元素。
class Solution {
public int kthSmallest(TreeNode root, int k) {
int left = sumTree(root.left);
if (left + 1 == k) return root.val;
else if (k <= left) return kthSmallest(root.left, k);
else return kthSmallest(root.right, k - left - 1);
}
public int sumTree(TreeNode root) {
if (root == null) return 0;
return sumTree(root.left) + sumTree(root.right) + 1;
}
}450.删除二叉搜索树中的节点
这题通过遍历就可以找到需要删除的节点，这题的难点是怎样删除找到的节点。
确认了需要删除的节点后，就要先找到该节点右子树最小的值，用该值代替删除的节点，因为这样就不会破环二叉搜索树的结构了。（也可以寻找左子树的最大值）
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 寻找节点右子树的最小值
TreeNode node = root.right;
while (node.left != null) node = node.left;
// 将节点的左子树赋值给最小值的左子树完成删除
node.left = root.left;
return root.right;
} else if (key > root.val) {
root.right = deleteNode(root.right,key);
} else {
root.left = deleteNode(root.left,key);
}
return root;
}
}538. 把二叉搜索树转换为累加树
这题主要的问题是没理解题目到底在讲什么，看了答案才知道其实是将树从下到上，从右到左累加，然后将该值赋值给当前节点。
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root == null) return null;
convertBST(root.right);
// 将累加结果赋值给当前节点，并记录累加
root.val = root.val + sum;
sum = root.val;
convertBST(root.left);
return root;
}
}589.N叉树的前序遍历
递归
- 判断root是否为空结点
- 将数据存入List
- 递归前序遍历各个结点
这道题难的就是结果的存储了，因为经常写的前序遍历都是直接输出结果的，存储的化就要全局的List了。
public 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，将当前结点的孩子压入栈
public class Solution {
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
Node node = stack.pop();
list.add(node.val);
for (int i = node.children.size() - 1; i >= 0; i--) {
stack.push(node.children.get(i));
}
}
return list;
}
}652.寻找重复的子树
这题主要的难点就是怎样判断该节点的子树和其他节点的子树是否一样。
可以考虑到的是将该节点的子树和根作为一个字符串，如果其他字符串与其一样，就判断为这是重复的子树节点。
class Solution {
// 用来去重
HashMap<String,Integer> map = new HashMap<>(16);
List<TreeNode> res = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
return res;
}
public String traverse(TreeNode root) {
if(root == null) {
return "#";
}
String left = traverse(root.left);
String right = traverse(root.right);
String str = left + "+" + right + "+" + root.val;
int freq = map.getOrDefault(str,0);
// 不重复将值加入到List中
if (freq == 1) res.add(root);
map.put(str,freq + 1);
return str;
}
}897.递增顺序查找树
直接中序遍历然后把节点赋给结果子树的右子树就好了。
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;
}
}938.二叉搜索树的范围和
暴力递归破解。
class Solution {
int sum = 0;
public int rangeSumBST(TreeNode root, int low, int high) {
range(root,low,high);
return sum;
}
public void range(TreeNode root,int low,int high) {
if (root == null) return;
range(root.left,low,high);
if (root.val >= low && root.val <= high) sum += root.val;
range(root.right,low,high);
}
}因为中序遍历是从小到大的，所以还可以优化一下。
965.单值二叉树
class Solution {
public boolean isUnivalTree(TreeNode root) {
return isTree(root,root.val);
}
public boolean isTree(TreeNode root,int val) {
if (root == null) return true;
if (root.val != val) return false;
return isTree(root.left,root.val) && isTree(root.right,root.val);
}
}从根到叶的二进制数之和
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大的节点，虽然效率不这么好，但是也是一种方法。
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);
}
}中序遍历
因为给的树是二叉搜索树，所以应该想到二叉搜索树的中序遍历就是有序的，所以可以省去排序的时间。
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个结点就可以了。
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题就行。
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);
}
}这种解法速度还是很快的，只是消耗的内存有点多，可能题目就打算消耗多的内存。还有一种思路就是使用层次遍历，其实也差不多。也看了一下其他解法，不过很多的解法消耗的内存有点多，然后看到一些内存消耗低的解法，发现寻找深度的代码还可以优化，然后又优化了一些细节。
class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
int depth = maxDepth(tree);
ListNode[] list = new ListNode[depth];
if (tree == null) return list;
listofdepth(tree,0,list);
return list;
}
public int maxDepth(TreeNode node) {
if (node == null) return 0;
return Math.max(maxDepth(node.left),maxDepth(node.right)) + 1;
}
public void listofdepth(TreeNode root,int k,ListNode[] list) {
if (root == null) return;
ListNode node = new ListNode(root.val);
node.next = list[k];
list[k] = node;
listofdepth(root.right,k + 1,list);
listofdepth(root.left,k + 1,list);
}
}