登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›hot100之二叉树下

hot100之二叉树下

凉砧掌 2025-6-19 20:21:21
二叉树的右视图(199)
  1. class Solution {
  2.     List<Integer> res = new ArrayList<>();
  3.     public List<Integer> rightSideView(TreeNode root) {
  4.         dfs(root, 0);
  5.         return res;
  6.     }
  7.     private void dfs(TreeNode node, int depth){
  8.         if (node == null) return;
  10.         if (res.size() == depth){
  11.             res.add(node.val);
  12.         }
  13.         
  14.         dfs(node.right, depth+1);
  15.         dfs(node.left, depth+1);
  16.     }
  17. }
复制代码

  • 分析
因为一层只需要一个节点, 以depth作为限制
二叉树展开为链表(114)
  1. class Solution {
  2.     public void flatten(TreeNode root) {
  3.         if (root == null) return;
  4.         
  5.         flatten(root.left);
  6.         flatten(root.right);
  7.         TreeNode lef = root.left;
  8.         TreeNode rig = root.right;
  10.         root.left = null;
  11.         root.right = lef;
  12.         TreeNode curr = root;
  13.         
  14.         while (curr.right != null){
  15.             curr = curr.right;
  16.         }curr.right = rig;
  18.     }
  19. }
复制代码

  • 分析
将左子树截断放到右端, 再将右子树放在左子树末尾
因为递归原因, 左子树必然为链表
从前序与中序遍历序列构造二叉树(105)
  1. class Solution {
  2.     Map<Integer, Integer> map;
  3.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  4.         int n = preorder.length;
  5.         map = new HashMap<>();
  6.         for (int i = 0; i < n; i++){
  7.             map.put(inorder[i], i);
  8.         }
  10.         return dfs(preorder, 0, n, 0, n);
  11.     }
  13.     private TreeNode dfs(int[] preorder, int lefPre, int rigPre, int lefIn, int rigIn){
  14.         if (lefPre == rigPre) return null;
  16.         int lefSize = map.get(preorder[lefPre]) - lefIn;
  17.         TreeNode lefNode = dfs(preorder, lefPre+1, lefPre+1+lefSize, lefIn, lefIn+lefSize);
  18.         TreeNode rigNode = dfs(preorder, lefPre+1+lefSize, rigPre, lefIn+1+lefSize, rigIn);
  19.         return new TreeNode(preorder[lefPre], lefNode, rigNode);
  20.     }
  21. }
复制代码

  • 分析
以前序遍历取根, 切分中序遍历的左右子树作构造
路径总和(437)
  1. class Solution {
  2.     Map<Long, Integer> map = new HashMap<>();
  3.     int res;
  4.     public int pathSum(TreeNode root, int targetSum) {
  5.         map.put(0L,1);
  6.         dfs(root, targetSum, 0L);
  7.         return res;
  8.     }
  10.     private void dfs(TreeNode node, int targetSum, long subSum){
  11.         if (node == null) return;
  12.         subSum += node.val;
  13.         if (map.containsKey(subSum - targetSum)) res +=map.get(subSum - targetSum);
  14.         map.put(subSum, map.getOrDefault(subSum, 0)+1);
  15.         dfs(node.left, targetSum, subSum);
  16.         dfs(node.right, targetSum, subSum);
  17.         map.put(subSum, map.get(subSum)-1);
  18.     }
  19. }
复制代码

  • 分析
又是一个前缀和题目
二叉树的最近公共祖先(236)
  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if (root == null || p == root || q == root) return root;
  5.         TreeNode lefNode = lowestCommonAncestor(root.left, p, q);
  6.         TreeNode rigNode = lowestCommonAncestor(root.right, p, q);
  8.         if (lefNode == null && rigNode == null) return null;
  9.         if (lefNode != null && rigNode != null) return root;
  11.         return lefNode != null ? lefNode : rigNode;
  13.     }
  14. }
复制代码

  • 分析
找到子节点向上return, 两节点未相遇则继续向上return

  • 感悟
二叉树题目要注意需要返回给父节点的元素
二叉树中的最大路径和(124)
  1. class Solution {
  2.     int res = Integer.MIN_VALUE;
  3.     public int maxPathSum(TreeNode root) {
  4.         dfs(root);
  5.         return res;
  6.     }
  7.     private int dfs(TreeNode node){
  8.         if (node == null) return 0;
  10.         int lefMax = Math.max(dfs(node.left), 0);
  11.         int rigMax = Math.max(dfs(node.right), 0);
  13.         res = Math.max(res, lefMax+ node.val + rigMax);
  14.         return Math.max(lefMax, rigMax) + node.val;
  15.     }
  16. }
复制代码

  • 分析
以单向链作返回父节点元素, 取 左右链+节点 与记录的最大值作对比

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
凉砧掌
2025-6-19 20:21:21

0

粉丝关注

13

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫