文章目录
树的几种遍历方式
剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
（请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。）
https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return check(root.left,root.right);
}
private boolean check(TreeNode L,TreeNode R){
if(L == null && R == null){
return true;
}
if(L == null || R == null){
return false;
}
return L.val == R.val
&& check(L.left,R.right)
&& check(L.right,R.left);
}
}
- 时间：O(n)
- 空间：O(n)
450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
https://leetcode-cn.com/problems/delete-node-in-a-bst/
思路：
class Solution {
private int rightMin(TreeNode root) {
TreeNode tmp = root;
while (tmp.left != null) {
tmp = tmp.left;
}
return tmp.val;
}
private int leftMax(TreeNode root) {
TreeNode tmp = root;
while (tmp.right != null) {
tmp = tmp.right;
}
return tmp.val;
}
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key > root.val) {
//4.如果查找的结点比根节点大，继续在右子树查找删除该结点
root.right = deleteNode(root.right, key);
} else if (key < root.val) {
root.left = deleteNode(root.left, key);
} else {
//6.如果找到了该结点，删除它
if (root.left == null && root.right == null) {
root = null;
} else if (root.right != null) {
// 找到 右子树下最小的一个节点 替换 root 即可
root.val = rightMin(root.right);
//4.如果查找的结点比根节点大，继续在右子树查找删除该结点
root.right = deleteNode(root.right, root.val);
} else if (root.left != null) {
// 找到 左子树下最大的一个节点 替换 root 即可
root.val = leftMax(root.left);
root.left = deleteNode(root.left, root.val);
}
}
return root;
}
}
- 时间：O(logN)
- 空间：O(H)
1448. 统计二叉树中好节点的数目
https://leetcode-cn.com/problems/count-good-nodes-in-binary-tree/
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
思路：DFS，但是需要保存从根节点DFS下来的最大值，判断如果大于等于最大值，那么结果+1
class Solution {
int ans = 0;
public int goodNodes(TreeNode root) {
inOrder(root, Integer.MIN_VALUE);
return ans;
}
// max是父亲路径上的最大值
public void inOrder(TreeNode root, int max) {
if (root == null) {
return;
}
if (root.val >= max) {
ans++;
max = root.val;
}
inOrder(root.left, max);
inOrder(root.right, max);
}
}
剑指 Offer 26. 树的子结构
https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
class Solution {
boolean sameTree(TreeNode A, TreeNode B) {
// 要注意先判断 B，不然会运行不通过
if (B == null)
return true;
if (A == null)
return false;
if (A.val == B.val) {
return sameTree(A.left, B.left) && sameTree(A.right, B.right);
} else {
return false;
}
}
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null)
return false;
// 先判断当前
if (A.val == B.val) {
// 坑点：这里返回 true 才 返回，否则就要进行下面的判断！
boolean ret = sameTree(A.left, B.left) && sameTree(A.right, B.right);
if (ret) {
return true;
}
}
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
}
剑指 Offer 28. 对称的二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return check(root.left,root.right);
}
private boolean check(TreeNode L,TreeNode R){
if(L == null && R == null){
return true;
}
if(L == null || R == null){
return false;
}
return L.val == R.val
&& check(L.left,R.right)
&& check(L.right,R.left);
}
}
剑指 Offer 27. 二叉树的镜像
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root != null){
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
mirrorTree(root.left);
mirrorTree(root.right);
}
return root;
}
}
199. 二叉树的右视图
class Solution {
private List<Integer> res = new LinkedList<>();
private void dfs(TreeNode root, int depth) {
if (root == null) {
return;
}
// 根节点 深度为0，依次类推 ~~
// 如果是已经访问过的情况：res.size() 会大于 depth
/**
* 如果当前节点所在深度还没有出现在res里，
* 说明在该深度下当前节点是第一个被访问的节点，
* 因此将当前节点加入res中。
* */
if (depth == res.size()) {
res.add(root.val);
}
dfs(root.right, depth + 1);
dfs(root.left, depth + 1);
}
public List<Integer> rightSideView(TreeNode root) {
if (root == null) {
return res;
}
dfs(root, 0);
return res;
}
}
- 时间：O(n)
- 空间：O(n)
剑指 Offer II 050. 向下的路径节点之和
O(n^2) 的二叉树节点遍历
class Solution {
private int dfs(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
int ret = 0;
if (root.val == targetSum) {
ret++;
}
// 比较巧妙的解法：targetSum - root.val
ret += dfs(root.left, targetSum - root.val);
ret += dfs(root.right, targetSum - root.val);
return ret;
}
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
int ret = dfs(root, targetSum);
ret += pathSum(root.left, targetSum);
ret += pathSum(root.right, targetSum);
return ret;
}
}
- 空间 O(n)
思路二：利用前缀和算法
见： leetcode 题解
剑指 Offer 55 - II. 平衡二叉树
https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
方法二：自底向上的递归
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
- 时间：O(n)
- 空间：O(n)
98. 验证二叉搜索树
https://leetcode-cn.com/problems/validate-binary-search-tree/
思路：中序遍历如果是得到一个排序好的数组的话，那么肯定就是二叉搜索树
这里其实直接对比前一个节点和当前节点即可，不用把所有遍历过的节点都记录下来。
class Solution {
// 记录上一个节点的值，初始值为Long的最小值
private long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
// 中序遍历 左中右
boolean left = isValidBST(root.left);
if (root.val <= pre) return false;
pre = root.val;
boolean right = isValidBST(root.right);
return left && right;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
思路：递归，如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
class Solution {
private boolean helper(TreeNode root, Integer min, Integer max) {
if (root == null) {
return true;
}
if (min != null && min >= root.val) return false;
if (max != null && max <= root.val) return false;
return helper(root.left, min, root.val) && helper(root.right, root.val, max);
}
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n)。
235. 最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
时间O(n)，空间O(n)
思路见：剑指 offer 全记录
-8.树中两个节点的最近公共祖先 lowest-common-ancestor问题
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) {
return root;
}
TreeNode left_lca = lowestCommonAncestor(root.left, p, q);
TreeNode right_lca = lowestCommonAncestor(root.right, p, q);
if (left_lca != null && right_lca != null) {
return root;
}
return left_lca != null ? left_lca : right_lca;
}
}
104. 求最小深度和最大深度
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
思路：DFS 搜索
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return left > right ? left + 1 : right + 1;
}
}
- 时间：O(n)
- 空间：O(height)
思路：BFS 搜索
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int maxDeep = 0;
while (!queue.isEmpty()) {
if (!queue.isEmpty()) {
maxDeep++;
}
// 让这一层的节点全部出队列(注意这里需要记录下来size，然后for循环直接队头出队列)
int length = queue.size();
for (int i = 0; i < length; i++) {
TreeNode top = queue.poll();
if (top.left != null) queue.offer(top.left);
if (top.right != null) queue.offer(top.right);
}
}
return maxDeep;
}
}
- 时间复杂度：O(n)
- 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。
652. 寻找重复的子树
https://leetcode-cn.com/problems/find-duplicate-subtrees/
思路：
使用深度优先搜索，其中递归函数返回当前子树的序列化结果。把每个节点开始的子树序列化结果保存在 map 中，然后判断是否存在重复的子树。
class Solution {
private List<TreeNode> result = new LinkedList<>();
// 子树的序列化String : 出现的次数
private HashMap<String, Integer> countMap = new HashMap<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
if (root == null) {
return result;
}
dfs(root);
return result;
}
private String dfs(TreeNode node) {
if (node == null) {
return "#";
}
String str = node.val + "," + dfs(node.left) + "," + dfs(node.right);
countMap.put(str, countMap.getOrDefault(str, 0) + 1);
if (countMap.get(str) == 2) {
result.add(node);
}
return str;
}
}
- 时间：O(n^2)
- 空间：O(n^2)