Leetcode树
2020-10-13 本文已影响0人
1nvad3r
94. 二叉树的中序遍历
class Solution {
List<Integer> res = new ArrayList<>();
void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
res.add(root.val);
inOrder(root.right);
}
public List<Integer> inorderTraversal(TreeNode root) {
inOrder(root);
return res;
}
}
使用栈：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
95. 不同的二叉搜索树 II
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n < 1) {
return new ArrayList<>();
}
return helper(1, n);
}
public List<TreeNode> helper(int start, int end) {
List<TreeNode> res = new ArrayList<>();
if (start > end) {
res.add(null);
return res;
}
for (int i = start; i <= end; i++) {
List<TreeNode> left = helper(start, i - 1);
List<TreeNode> right = helper(i + 1, end);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
}
96. 不同的二叉搜索树
可以直接使用卡特兰数的公式。
也可以使用动态规划dp[i]代表i个数组成的二叉搜索树的个数。
class Solution {
public int numTrees(int n) {
if (n == 0) {
return 0;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[n];
}
}
98. 验证二叉搜索树
class Solution {
long pre = Long.MIN_VALUE;
public boolean inOrder(TreeNode root) {
if (root == null) {
return true;
}
if (inOrder(root.left) == false) {
return false;
}
if (root.val > pre) {
pre = root.val;
} else {
return false;
}
if (inOrder(root.right) == false) {
return false;
}
return true;
}
public boolean isValidBST(TreeNode root) {
return inOrder(root);
}
}
99. 恢复二叉搜索树
class Solution {
TreeNode first, second;
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
if (root.val < pre.val && first == null) {
first = pre;
}
if (root.val < pre.val && first != null) {
second = root;
}
pre = root;
inOrder(root.right);
}
public void recoverTree(TreeNode root) {
inOrder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}
100. 相同的树
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(q.right, q.right);
}
}
102. 二叉树的层序遍历
主要思想是使用current记录当前层的结点个数，next记录下一层的结点个数。
当current减至0时，说明该记录下一层了。令current = next , next = 0。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>(new ArrayList<>());
}
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int current = 1, next = 0;//当前层和下一层的结点个数
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode front = queue.poll();
list.add(front.val);
if (front.left != null) {
queue.offer(front.left);
next++;
}
if (front.right != null) {
queue.offer(front.right);
next++;
}
current--;
if (current == 0) {
res.add(new ArrayList<>(list));
list.clear();
current = next;
next = 0;
}
}
return res;
}
}
103. 二叉树的锯齿形层次遍历
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>(new ArrayList<>());
}
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
int current = 1, next = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int flag = 1;
while (!queue.isEmpty()) {
TreeNode front = queue.poll();
temp.add(front.val);
current--;
if (front.left != null) {
queue.offer(front.left);
next++;
}
if (front.right != null) {
queue.offer(front.right);
next++;
}
if (current == 0) {
if (flag % 2 == 1) {
res.add(new ArrayList<>(temp));
} else {
Collections.reverse(temp);
res.add(new ArrayList<>(temp));
}
flag++;
temp.clear();
current = next;
next = 0;
}
}
return res;
}
}
104. 二叉树的最大深度
class Solution {
int max = 0;
public void preOrder(TreeNode root, int depth) {
if (root == null) {
return;
}
max = Math.max(max, depth);
preOrder(root.left, depth + 1);
preOrder(root.right, depth + 1);
}
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
preOrder(root, 1);
return max;
}
}
105. 从前序与中序遍历序列构造二叉树
class Solution {
public TreeNode helper(int[] preorder, int[] inorder, int preL, int preR, int inL, int inR) {
if (preL > preR || inL > inR) {
return null;
}
int rootVal = preorder[preL];
TreeNode root = new TreeNode(rootVal);
int index;//根结点在中序序列中的位置
for (index = inL; index <= inR; index++) {
if (inorder[index] == rootVal) {
break;
}
}
int numLeft = index - inL;//左子树结点个数
root.left = helper(preorder, inorder, preL + 1, preL + numLeft, inL, index - 1);
root.right = helper(preorder, inorder, preL + numLeft + 1, preR, index + 1, inR);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
}
106. 从中序与后序遍历序列构造二叉树
class Solution {
public TreeNode helper(int[] inorder, int[] postorder, int inL, int inR, int postL, int postR) {
if (inL > inR) {
return null;
}
int rootVal = postorder[postR];
TreeNode root = new TreeNode(rootVal);
int index;//根结点在中序遍历中的位置
for (index = inL; index <= inR; index++) {
if (inorder[index] == rootVal) {
break;
}
}
int numLeft = index - inL;//左子树个数
root.left = helper(inorder, postorder, inL, inL + numLeft - 1, postL, postL + numLeft - 1);
root.right = helper(inorder, postorder, index + 1, inR, postL + numLeft, postR - 1);
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
}
107. 二叉树的层次遍历 II
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null) {
return new ArrayList<>(new ArrayList<>());
}
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int current = 1, next = 0;
while (!queue.isEmpty()) {
TreeNode front = queue.poll();
temp.add(front.val);
current--;
if (front.left != null) {
queue.offer(front.left);
next++;
}
if (front.right != null) {
queue.offer(front.right);
next++;
}
if (current == 0) {
res.add(new ArrayList<>(temp));
temp.clear();
current = next;
next = 0;
}
}
Collections.reverse(res);
return res;
}
}
108. 将有序数组转换为二叉搜索树
class Solution {
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int rootIndex = (left + right) / 2;
TreeNode root = new TreeNode(nums[rootIndex]);
root.left = helper(nums, left, rootIndex - 1);
root.right = helper(nums, rootIndex + 1, right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
}
110. 平衡二叉树
class Solution {
int maxDepth;
public void preOrder(TreeNode root, int depth) {
if (root == null) {
return;
}
maxDepth = Math.max(maxDepth, depth);
preOrder(root.left, depth + 1);
preOrder(root.right, depth + 1);
}
public int calDepth(TreeNode root) {
if (root == null) {
return 0;
}
maxDepth = 1;
preOrder(root, 1);
return maxDepth;
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int left = calDepth(root.left);
int right = calDepth(root.right);
if (Math.abs(left - right) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
}
改进版本：
class Solution {
public int height(TreeNode root) {
if (root == null) {
return 0;
} else {
return Math.max(height(root.left), height(root.right)) + 1;
}
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
if (Math.abs(height(root.left) - height(root.right)) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
}
111. 二叉树的最小深度
class Solution {
int res = Integer.MAX_VALUE;
public void dfs(TreeNode root, int depth) {
if (root == null) {
return;
}
dfs(root.left, depth + 1);
if (root.left == null && root.right == null) {
res = Math.min(res, depth);
}
dfs(root.right, depth + 1);
}
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root, 1);
return res;
}
}
112. 路径总和
class Solution {
public boolean res = false;
public void dfs(TreeNode root, int sum) {
if (root == null) {
return;
}
sum -= root.val;
if (root.left == null && root.right == null && sum == 0) {
res = true;
}
dfs(root.left, sum);
dfs(root.right, sum);
}
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
dfs(root, sum);
return res;
}
}
113. 路径总和 II
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public void dfs(TreeNode root, int sum) {
if (root == null) {
return;
}
sum -= root.val;
temp.add(root.val);
if (root.left == null && root.right == null && sum == 0) {
res.add(new ArrayList<>(temp));
}
dfs(root.left, sum);
dfs(root.right, sum);
temp.remove(temp.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
dfs(root, sum);
return res;
}
}
114. 二叉树展开为链表
class Solution {
List<TreeNode> list = new ArrayList<>();
public void dfs(TreeNode root) {
if (root == null) {
return;
}
list.add(root);
dfs(root.left);
dfs(root.right);
}
public void flatten(TreeNode root) {
if (root == null) {
return;
}
dfs(root);
TreeNode cur = root;
cur.left = cur.right = null;
for (int i = 1; i < list.size(); i++) {
cur.left = null;
cur.right = list.get(i);
cur = cur.right;
}
}
}
改进：空间复杂度O(1)
对于当前节点，如果其左子节点不为空，则在其左子树中找到最右边的节点，作为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点都处理结束。
class Solution {
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode next = curr.left;
TreeNode predecessor = next;
while (predecessor.right != null) {
predecessor = predecessor.right;
}
predecessor.right = curr.right;
curr.left = null;
curr.right = next;
}
curr = curr.right;
}
}
}
116. 填充每个节点的下一个右侧节点指针
class Solution {
public void bfs(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
if (i < size - 1) {
node.next = queue.peek();
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
public Node connect(Node root) {
bfs(root);
return root;
}
}
117. 填充每个节点的下一个右侧节点指针 II
class Solution {
public void bfs(Node root) {
if (root == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
if (i < size - 1) {
node.next = queue.peek();
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
public Node connect(Node root) {
bfs(root);
return root;
}
}
124. 二叉树中的最大路径和
129. 求根到叶子节点数字之和
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public void dfs(TreeNode root) {
if (root == null) {
return;
}
temp.add(root.val);
if (root.left == null && root.right == null) {
res.add(new ArrayList<>(temp));
}
dfs(root.left);
dfs(root.right);
temp.remove(temp.size() - 1);
}
public int sumNumbers(TreeNode root) {
dfs(root);
int sum = 0;
for (List<Integer> list : res) {
StringBuilder sb = new StringBuilder();
for (Integer i : list) {
sb.append(i);
}
sum += Integer.parseInt(sb.toString());
}
return sum;
}
}
改进：
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
private int dfs(TreeNode root, int i) {
if (root == null) {
return 0;//1、节点为空
}
int res = i * 10 + root.val;
if (root.left == null && root.right == null) {
return res;//2、节点为叶子节点
}
return dfs(root.left, res) + dfs(root.right, res);//3、节点为非叶子节点
}
}
144. 二叉树的前序遍历
class Solution {
List<Integer> res = new ArrayList<>();
public void dfs(TreeNode root) {
if (root == null) {
return;
}
res.add(root.val);
dfs(root.left);
dfs(root.right);
}
public List<Integer> preorderTraversal(TreeNode root) {
dfs(root);
return res;
}
}
使用栈：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode top = stack.poll();
res.add(top.val);
if (top.right != null) {
stack.push(top.right);
}
if (top.left != null) {
stack.push(top.left);
}
}
return res;
}
}
145. 二叉树的后序遍历
class Solution {
List<Integer> res = new ArrayList<>();
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
res.add(root.val);
}
public List<Integer> postorderTraversal(TreeNode root) {
postOrder(root);
return res;
}
}
使用栈：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
}
173. 二叉搜索树迭代器
class BSTIterator {
List<Integer> list = new ArrayList<>();
int index = 0;
public BSTIterator(TreeNode root) {
inOrder(root);
}
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
/**
* @return the next smallest number
*/
public int next() {
return list.get(index++);
}
/**
* @return whether we have a next smallest number
*/
public boolean hasNext() {
return index < list.size();
}
}
199. 二叉树的右视图
class Solution {
List<Integer> res = new ArrayList<>();
public void bfs(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode front = queue.poll();
if (front.left != null) {
queue.offer(front.left);
}
if (front.right != null) {
queue.offer(front.right);
}
if (i == size - 1) {
res.add(front.val);
}
}
}
}
public List<Integer> rightSideView(TreeNode root) {
bfs(root);
return res;
}
}
222. 完全二叉树的节点个数
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
226. 翻转二叉树
class Solution {
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
public TreeNode invertTree(TreeNode root) {
postOrder(root);
return root;
}
}
230. 二叉搜索树中第K小的元素
class Solution {
List<Integer> list = new ArrayList<>();
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
public int kthSmallest(TreeNode root, int k) {
inOrder(root);
return list.get(k - 1);
}
}
235. 二叉搜索树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (true) {
if (p.val < root.val && q.val < root.val) {
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
root = root.right;
} else {
break;
}
}
return root;
}
}
236. 二叉树的最近公共祖先
class Solution {
List<TreeNode> temp = new ArrayList<>();
List<List<TreeNode>> res = new ArrayList<>();
public void dfs(TreeNode root, TreeNode target) {
if (root == null) {
return;
}
temp.add(root);
if (root.val == target.val) {
res.add(new ArrayList<>(temp));
}
dfs(root.left, target);
dfs(root.right, target);
temp.remove(temp.size() - 1);
}
public void getAncestor(TreeNode root, TreeNode target) {
temp.clear();
dfs(root, target);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
getAncestor(root, p);
getAncestor(root, q);
List<TreeNode> pAncestor = res.get(0);
List<TreeNode> qAncestor = res.get(1);
int size = Math.min(pAncestor.size(), qAncestor.size());
for (int i = 0; i < size; i++) {
if (pAncestor.get(i).val == qAncestor.get(i).val && i != size - 1) {
continue;
} else if (pAncestor.get(i).val == qAncestor.get(i).val && i == size - 1) {
return pAncestor.get(i);
} else {
return pAncestor.get(i - 1);
}
}
return qAncestor.get(0);
}
}
改进：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}
257. 二叉树的所有路径
class Solution {
List<String> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public void dfs(TreeNode root) {
if (root == null) {
return;
}
temp.add(root.val);
if (root.left == null && root.right == null) {
StringBuilder sb = new StringBuilder();
for (Integer i : temp) {
sb.append(i);
sb.append("->");
}
sb.deleteCharAt(sb.length() - 1);
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
}
dfs(root.left);
dfs(root.right);
temp.remove(temp.size() - 1);
}
public List<String> binaryTreePaths(TreeNode root) {
dfs(root);
return res;
}
}
297. 二叉树的序列化与反序列化
序列化的思路是利用层次遍历，不管左右子树为不为空，都加入到队列中去。出队时判断是否为空，为空则字符串加“null”。
反序列化的思路是用一个队列存储所有的父结点，然后遍历所有的结点，只要不为null，则加到父结点上，且入队。
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "null";
}
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode front = queue.poll();
if (front == null) {
sb.append("null,");
continue;
} else {
sb.append(front.val + ",");
}
queue.add(front.left);
queue.add(front.right);
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if ("null".equals(data)) {
return null;
}
String[] split = data.split(",");
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(split[0]));
queue.add(root);
for (int i = 1; i < split.length; i++) {
TreeNode front = queue.poll();
if (!"null".equals(split[i])) {
TreeNode left = new TreeNode(Integer.parseInt(split[i]));
front.left = left;
queue.add(left);
}
if (!"null".equals(split[++i])) {
TreeNode right = new TreeNode(Integer.parseInt(split[i]));
front.right = right;
queue.add(right);
}
}
return root;
}
}
