二叉树
前中后序遍历是树的基础, 关于树的题目首先要想好到底是用哪种遍历的思想, 遍历通常有三种实现方式, 以前序遍历举例.
递归实现
最常用的方式.
class Solution {
List<Integer> res = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) return new ArrayList<Integer>(); // base
// pre, 功能部分可以替换
res.add(root.val);
// function
preorderTraversal(root.left);
preorderTraversal(root.right);
// result
return res;
}
}
栈实现
相当于DFS去搜索.
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
res.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return res;
}
}
Morris遍历
在线性时间情况下, 以$O(1)$的空间复杂度遍历. 来自论文Traversing Binary Trees Simply and Cheaply.
//todo
递归三步: 1.理解函数功能, 2.函数的参数啥意思, 3.得到递归结果后怎么操作(用前/中/后序哪一个).
二叉树题目
二叉树步骤:
- 哪种遍历(自顶向下还是自底向上/要不要构造或找到root节点), 决定功能区的位置
- 功能区方法
- 边界条件, 通常是遍历到
null值时做判断 - 返回的值或void不需要返回, 有返回值的遍历通常要把返回的值用指针指向
- 我们有时候会单纯地用一个方法作为拼接/断开等操作的载体, 这个方法通常不需要返回值
297. 二叉树的序列化与反序列化
前序, 后序都可以, 因为deserialize的时候需要知道root的位置, 所以中序没法用.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("#,");
return;
}
//pre
sb.append(root.val).append(",");
serialize(root.left, sb);
serialize(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
LinkedList<String> list = new LinkedList<>();
for (String s: data.split(",")) {
list.add(s);
}
return deserialize(list);
}
private TreeNode deserialize(LinkedList<String> list) {
if (list.isEmpty()) return null;
//pre
String val = list.removeFirst();
if (val.equals("#")) return null;
TreeNode root = new TreeNode(Integer.parseInt(val));
root.left = deserialize(list);
root.right = deserialize(list);
return root;
}
}
226. 翻转二叉树
root不能动, 前序遍历交换左右子树.
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
//pre
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.right);
invertTree(root.left);
return root;
}
}
或者
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}
也可以自底向上, 后序遍历交换左右子树.
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
//post
root.left = right;
root.right = left;
return root;
}
}
114. 二叉树展开为链表
要断开左子树接到右边, 所以从自底向上的方向考虑, 那么就需要后序遍历.
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.left);
flatten(root.right);
//post
TreeNode right = root.right;
root.right = root.left;
root.left = null;
while (root.right != null) root = root.right;
root.right = right;
}
}
116. 填充每个节点的下一个右侧节点指针
连接每个节点的子节点, 以及相邻父节点的子节点, 自顶向下考虑, 那么连接函数就必须是前序遍历. 把第二层左边当做node1, 右边当成node2即可.
class Solution {
public Node connect(Node root) {
if (root == null) return null;
connect(root.left, root.right);
return root;
}
private void connect(Node node1, Node node2) {
if (node1 == null || node2 == null) return;
//pre
node1.next = node2;
connect(node1.left, node1.right);
connect(node2.left, node2.right);
connect(node1.right, node2.left);
}
}
654. 最大二叉树
构造树, 自然想到自顶向下从root开始构造, 所以前序遍历. 要用最大值划分数组, 所以要划分数组.
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree(nums, 0, nums.length - 1);
}
private TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
if (start > end) return null;
//pre
int maxIndex = -1, maxValue = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
if (nums[i] > maxValue) {
maxIndex = i;
maxValue = nums[i];
}
}
TreeNode root = new TreeNode(maxValue);
root.left = constructMaximumBinaryTree(nums, start, maxIndex - 1);
root.right = constructMaximumBinaryTree(nums, maxIndex + 1, end);
return root;
}
}
105. 从前序与中序遍历序列构造二叉树
同上, 根绝前序找root, 根据中序算左右子树的大小.
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int prestart, int preend, int instart, int inend) {
if (prestart > preend) return null;
//pre
int rootval = preorder[prestart];
int index = instart;
while (inorder[index] != rootval) index++;
//size of left and right trees
int leftsize = index - instart;
int rightsize = inend - index;
TreeNode root = new TreeNode(rootval);
root.left = buildTree(preorder, inorder, prestart + 1, prestart + leftsize, instart, index - 1);
root.right = buildTree(preorder, inorder, prestart + leftsize + 1, preend, index + 1, inend);
return root;
}
}
106. 从中序与后序遍历序列构造二叉树
同上, 只不过rootval从最后一个开始.
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
private TreeNode buildTree(int[] inorder, int[] postorder, int instart, int inend, int poststart, int postend) {
if (poststart > postend) return null;
//pre
int rootval = postorder[postend], index = instart;
while(inorder[index] != rootval) index++;
int leftsize = index - instart;
TreeNode root = new TreeNode(rootval);
root.left = buildTree(inorder, postorder, instart, index - 1, poststart, poststart + leftsize - 1);
root.right = buildTree(inorder, postorder, index + 1, inend, poststart + leftsize, postend - 1);
return root;
}
}
652.寻找重复的子树
从叶子往跟找, 自底向上, 所以后序遍历. 为了避免重复要用HashMap来记录子树出现的次数, 形式同序列化的情况.
class Solution {
Map<String, Integer> map = new HashMap<>();
List<TreeNode> res = new LinkedList();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
find(root);
return res;
}
public String find(TreeNode root) {
if (root == null) return "#";
String left = find(root.left);
String right = find(root.right);
String tree = root.val + "," + left + "," + right; //root的值不能装中间
map.put(tree, map.getOrDefault(tree, 0) + 1);
if (map.get(tree) == 2) res.add(root);
return tree;
}
}
236. 二叉树的最近公共祖先
公共祖先, 从底往上找, 后序遍历. 左边没有右边没有就返回null, 两边都有就返回这个root.
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 && right == null) return null;
if(left == null) return right;
if(right == null) return left;
return root;
}
}
这个方法效果和上面一样, left == null和right == null都不成立就会返回root.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
//post
if (left == null) return right;
if (right == null) return left;
return root;
}
}
110. 平衡二叉树
计算高度, 并看每个子树是否符合要求.
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
二叉搜索树(BST)
230. 二叉搜索树中第K小的元素
中序遍历, 通过计数找第k小.
class Solution {
int res = -1;
int num = 0;
public int kthSmallest(TreeNode root, int k) {
kthSmallest2(root, k);
return res;
}
private void kthSmallest2(TreeNode root, int k) {
if (root == null) return;
kthSmallest(root.left, k);
//in
num++;
if (num == k) {
res = root.val;
return;
}
kthSmallest(root.right, k);
}
}
538/1038. 把二叉搜索树转换为累加树
中序遍历, 根据题意先遍历右边.
class Solution {
int num = 0;
public TreeNode bstToGst(TreeNode root) {
sum(root);
return root;
}
private void sum(TreeNode root) {
if (root == null) return;
sum(root.right);
//in
num += root.val;
root.val = num;
sum(root.left);
}
}
98. 验证二叉搜索树
中序遍历, 注意条件是左边的节点要小于右边的所有节点. 题目有大数问题, 用long解决(Long.MIN_VALUE也行).
class Solution {
long minVal = 0L;
public boolean isValidBST(TreeNode root) { //这一部分目的是找到左子树最小值
TreeNode node = root;
while (node.left != null) node = node.left;
minVal = (long)node.val - 1;
return isValidBST2(root);
}
public boolean isValidBST2(TreeNode root) {
if (root == null) return true;
if (!isValidBST2(root.left)) return false;
if (root.val <= minVal) return false;
else minVal = root.val;
if (!isValidBST2(root.right)) return false;
return true;
}
}
class Solution {
long minVal = 0L - Integer.MAX_VALUE - 2;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (!isValidBST(root.left)) return false;
if (root.val <= minVal) return false;
else minVal = root.val;
if (!isValidBST(root.right)) return false;
return true;
}
}
这个方法回避了最小值. 将root的值向下传递, 如果不传递那么子节点就不能和祖先节点比较.
class Solution {
boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) return true;
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
}
}
450. 删除二叉搜索树中的节点
通过值的大小来定向地遍历BST, 找到节点并删除. 增删改查都用此方法.
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
if (root.left == null && root.right == null) {
return null;
} else if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
TreeNode node = root.right;
while (node.left != null) node = node.left;
root.val = node.val;
root.right = deleteNode(root.right, root.val);
}
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else {
root.right = deleteNode(root.right, key);
}
return root;
}
}
701. 二叉搜索树中的插入操作
方法同上.
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (root.val > val) {
root.left = insertIntoBST(root.left, val);
} else if (root.val < val) {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
700. 二叉搜索树中的搜索
前两道题最基础的格式.
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) return null;
if (root.val == val) {
return root;
} else if (root.val > val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
}
参考
comments powered by Disqus