📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1250| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

[学Java/C#] 449题一个问题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
  1. public class Codec {
  2.    
  3.     public StringBuilder postorder(TreeNode root, StringBuilder sb) {
  4.         if (root == null)
  5.             return sb;
  6.         postorder(root.left, sb);
  7.         postorder(root.right, sb);
  8.         sb.append(root.val + ",");
  9.         
  10.         return sb;
  11.     }

  12.     // Encodes a tree to a single string.
  13.     public String serialize(TreeNode root) {
  14.         StringBuilder sb = postorder(root, new StringBuilder());
  15.         if (sb.length() > 0)
  16.             sb.deleteCharAt(sb.length() - 1);
  17.         return sb.toString();
  18.     }

  19.     ////////////////////////////////////////////////////////////////////////////////
  20.     ////////////////////////////////////////////////////////////////////////////////
  21.     ////////////////////////////////////////////////////////////////////////////////
  22.    
  23.     public TreeNode helper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
  24.         
  25.         if (nums.isEmpty())
  26.             return null;
  27.         
  28.         int val = nums.getLast();
  29.         
  30.         if (val < lower || val > upper)
  31.             return null;

  32.         nums.removeLast();
  33.         TreeNode root = new TreeNode(val);
  34.         
  35.         root.right = helper(val, upper, nums);
  36.         root.left = helper(lower, val, nums);
  37.         
  38.         return root;
  39.     }

  40.     // Decodes your encoded data to tree.
  41.     public TreeNode deserialize(String data) {
  42.         
  43.         if (data.isEmpty()) // value.length == 0;  
  44.             return null;
  45.         
  46.         ArrayDeque<Integer> nums = new ArrayDeque<Integer>();
  47.         
  48.         for (String s : data.split(","))
  49.             nums.add(Integer.valueOf(s));
  50.         
  51.         return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
  52.     }
  53. }
复制代码



想问下LeetCode 449题这个地方,32行的目的是什么呢?  如果超过范围,就返回null ?  什么时候回出现这个情况呢?


感谢各位大佬




补充内容 (2021-3-1 02:49):

https://youtu.be/V2zjW5AsSHQ   

上一篇:寻找LC contest rating 2200以上的朋友
下一篇:巨硬OA 高频题
🔗
wisdompeak2 2021-2-28 05:21:51 | 只看该作者
全局:
helper这个函数里,我们期待用nums里面的数构造一个BST子树,nums.last()是根,并且这棵树有上下界的限制。如果不满足,说明无法构成这棵BST子树。
回复

使用道具 举报

🔗
twtypsj 2021-2-28 08:12:39 | 只看该作者
全局:
wisdompeak2 发表于 2021-2-28 05:21
helper这个函数里,我们期待用nums里面的数构造一个BST子树,nums.last()是根,并且这棵树有上下界的限制。 ...

有道理,zszszs

评分

参与人数 1大米 +1 收起 理由
blackrose + 1 赞一个

查看全部评分

回复

使用道具 举报

🔗
 楼主| techDiscussion 2021-2-28 14:27:59 | 只看该作者
全局:
  1. public class Codec {

  2.     // Encodes a tree to a single string.
  3.     public String serialize(TreeNode root) {
  4.         
  5.         // root == null;
  6.         
  7.         StringBuilder sb = new StringBuilder();
  8.         
  9.         helper1(root, sb);
  10.         
  11.         return sb.toString();
  12.     }

  13.     public void helper1(TreeNode root, StringBuilder sb){
  14.         
  15.         if(root == null) return;    // we are doing postOrder --> left right middle
  16.         
  17.         helper1(root.left, sb);
  18.         helper1(root.right, sb);
  19.         
  20.         sb.append(root.val + ",");
  21.         
  22.     }
  23.    
  24.    
  25.     ////////////////////////////////////////////////////////////////
  26.     ////////////////////////////////////////////////////////////////
  27.     ////////////////////////////////////////////////////////////////
  28.    
  29.    
  30.     // Decodes your encoded data to tree.
  31.     public TreeNode deserialize(String data) {
  32.       
  33.         if(data.isEmpty()) return null;
  34.         
  35.         Deque<Integer> stack = new LinkedList<>();
  36.         
  37.         for(String curr : data.split(","))  stack.add(  Integer.valueOf(curr) );
  38.          
  39.         return helper2(Integer.MIN_VALUE, stack);         
  40.     }
  41.    
  42.     public TreeNode helper2(int lowerBound, Deque<Integer> stack){
  43.         
  44.         if(stack.isEmpty()) return null;
  45.         
  46.         int curr = stack.getLast();
  47.         
  48.         if(curr < lowerBound) return null;
  49.          
  50.         stack.removeLast();
  51.          
  52.         TreeNode root = new TreeNode(curr);
  53.          
  54.         root.right = helper2(curr, stack);
  55.         
  56.         root.left  = helper2(lowerBound, stack);
  57.         
  58.         return root;
  59.     }
  60.    
  61. }
复制代码


把代码更新了一下,其实根本不需要用到upper bound
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表