当前位置：首页 > news >正文

【数据结构与算法 | 灵神题单 | 自底向上DFS篇】力扣508, 1026, 951

news 来源：原创 2024/9/22 6:56:41

1. 力扣508：出现次数最多的子树元素和

1.1 题目：

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

示例 1：

输入: root = [5,2,-3]
输出: [2,-3,4]

示例 2：

输入: root = [5,2,-5]
输出: [2]

提示:

节点数在 [1, 104] 范围内
-105 <= Node.val <= 105

1.2 思路：

列表+哈希表+dfs递归

1.3 题解：

class Solution {// 列表用来存储所有出现次数最多的子树元素和List<Integer> list = new LinkedList<>();// 哈希表用来记录子树元素和出现的次数HashMap<Integer, Integer> map = new HashMap<>();// max用来记录子树元素和出现的最多次数int max;public int[] findFrequentTreeSum(TreeNode root) {// 节点数大于等于一个dfs(root);return toArr(list);}private int dfs(TreeNode node) {if(node == null) return 0;// 由定义：子树元素和等于该二叉树的所有节点之和node.val += dfs(node.left) + dfs(node.right);// 在哈希表中更新出现的元素和if(!map.containsKey(node.val)){map.put(node.val, 1);}else{map.put(node.val, 1+map.get(node.val));}int k = map.get(node.val);// 将原来的max值记录下来int old_max = max;// 再更新最新的maxmax = Integer.max(max, k);// 如果该节点的值（元素和）和之前的最多元素和一样// 那么就可以加入到列表中// 如果该元素和并不跟之前的意昂，反而是和已经更新过的元素和一样// 那么说明出现的新的最多元素和，将之前的列表清空，将该元素和加入到列表if(old_max == k){list.add(node.val);}else if (max == k){list.clear();list.add(node.val);}return node.val;}// 将列表转化为数组的方法private int[] toArr(List<Integer> list) {int[] arr = new int[list.size()];for(int i = 0; i < list.size(); i++){arr[i] = list.get(i);}return arr;}
}

2. 力扣1026：节点与其祖先之间的最大差值

2.1 题目：

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

示例 2：

输入：root = [1,null,2,null,0,3]
输出：3

提示：

树中的节点数在 2 到 5000 之间。
0 <= Node.val <= 105

2.2 思路：

比较简单，dfs自顶向下递归，用形参记录路径上的最大值和最小值。

2.3 题解：

class Solution {int diff;public int maxAncestorDiff(TreeNode root) {// 树节点大于等于2dfs(root, root.val, root.val);return diff;}// max和min记录遍历到该个节点前的路径的最大值和最小值private void dfs(TreeNode node, int max, int min) {if(node == null){return;}// 分别更新最大值和最小值if(node.val > max){max = node.val;}if(node.val < min){min = node.val;}int d = max - min;// 更新最大差值diff = Integer.max(d, diff);dfs(node.left, max, min);dfs(node.right, max, min);}
}

3. 力扣951：翻转等价二叉树

3.1 题目：

我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。

只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价 于二叉树 Y。

这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转等价 的函数，则返回 true ，否则返回 false 。

示例 1：

Flipped Trees Diagram

输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
输出：true
解释：我们翻转值为 1，3 以及 5 的三个节点。

示例 2:

输入: root1 = [], root2 = []
输出: true

示例 3:

输入: root1 = [], root2 = [1]
输出: false

提示：

每棵树节点数在 [0, 100] 范围内
每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数

3.2 思路：

认真考虑到翻转的每种情况即可。

3.3 题解：

class Solution {public boolean flipEquiv(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null){return true;}else if (root1 == null && root2 != null || root1 != null && root2 == null){return false;}return dfs(root1, root2);}private boolean dfs(TreeNode node1, TreeNode node2) {if(node1 == null && node2 == null){return true;}else if (node1 != null && node2 == null || node1 == null && node2 != null){return false;}// 遍历到节点的值都不一样，肯定是不对的if(node1.val != node2.val){return false;}// 考虑翻转的四种情况// 前两种一组，后两种一组if(node1.left != null && node2.left != null && node1.left.val != node2.left.val){TreeNode p1 = node1.left;TreeNode p2 = node1.right;node1.left = p2;node1.right = p1;}else if (node1.right != null && node2.right != null && node1.right.val != node2.right.val){TreeNode p1 = node1.left;TreeNode p2 = node1.right;node1.left = p2;node1.right = p1;} else if (node1.left != null && node2.left == null){TreeNode p = node1.left;node1.left = null;node1.right = p;}else if (node1.right != null && node2.right == null){TreeNode p = node1.right;node1.right = null;node1.left = p;}return dfs(node1.left, node2.left) && dfs(node1.right, node2.right);}
}