程序员不是做网站的,域名租赁网站,设计师网名女,google fonts wordpressLeetcode 606. 从二叉树构造字符串
题目描述 例子 小白做题
坐在自习室正在准备刷题的小白看到这道题#xff0c;想想自己那可是没少和白月光做题呢#xff0c;也不知道小美刷题刷到哪里了#xff0c;这题怎么还没来问我#xff0c;难道是王谦谦去做题了#xff1f;
这…Leetcode 606. 从二叉树构造字符串
题目描述 例子 小白做题
坐在自习室正在准备刷题的小白看到这道题想想自己那可是没少和白月光做题呢也不知道小美刷题刷到哪里了这题怎么还没来问我难道是王谦谦去做题了
这时候黑长直女神突然进到教室过来问小白你看到二叉树题目了吗这道606的题目感觉描述的很复杂好像是说树结构转换为字符串类型你有什么好思路吗
小白内心镇定这机会不就来了吗小美听说阮经天的《周处除三害》上映了有机会一起去看看吧 哦不是题目描述意思说的简单一些。
这种题目我们首先把他进行下条件梳理原来描述的是太复杂了而且题目拽了一堆转悠名词我们最好忽略它。 我们把之前的题目进行瘦身环节你是风儿我是沙让大片描述非走吧。 给定二叉树的根通过先序遍历的方式从二叉树构造一个由括号和整数组成的字符串并返回。 如果根的右节点为空则省略空括号对这不会影响二叉树的表示。 如果左节点为空并且右节点有一个值其中包含左节点的空括号如果省略左节点则会影响二叉树表示。
[1 null 2] -- 1(()(2)) 如果省略左侧 () 空括号则会影响二叉树 1(2) -- 表示左节点为 2右节点为 null
解题环节
树的题目我们首先按照递归的算法来考虑另外很重要的一点就是递归的终止条件。 所以我们要考虑根为null情况时候是返回空字符串的 if (root null) return “” case 0是要返回S字符串这种条件下左子树和右子树分别都是为空 case 1: 如果右子树为空返回左子树字符串 正常返回左子树与右子树的值。
考虑好条件后我们接下来考虑用StringBuilder来进行字符串的存储。
左子树的表达方式String left tree2str(root.left); 右子树的表达方式String right tree2str(root.right);
最后的重点来了就是如果右子树为空那么我们就返回空如果不为空那么我们就把右子树加入到string字符串中。
小美小伙子可以啊这不仅进行了解题阅读理解也有俩下子不过电影票要你买单哦。
小白没问题谁叫为了“真爱”呢。
真正面试环节
面试官你可以解答这道”从二叉树构造字符串“的题目吗来看看你对树结构的理解。
小白嘿嘿这不巧了么这不是。 public String tree2str(TreeNode root) {// 设置递归终结条件if(root null) return ;StringBuilder sb new StringBuilder();int val root.val;// 递归方法来找到左右子树的值String left tree2str(root.left);String right tree2str(root.right);sb.append(val);// 只有当左右子树都为空的时候才能忽略左子树// 否则就需要加入左子树, 就算是没有值也需要加上sb.append((left.isEmpty() right.isEmpty()) ? : (left));// 只有当右子树不为空的时候才加入右子树的值sb.append((right.isEmpty()) ? : (right));return sb.toString();}小明OK完事儿等着面试官来表扬自己吧。他肯定会说小子你是个好手工位都给你准备好了工资你说了算。
面试官矮油不错啊不过你这能不能写个测试啊。
小明OS今年这个找工市场人言洛阳花似锦偏我来时不逢春。。。不是怎么还让我些test case 啊 public static void main(String[] args) {TreeNode root new TreeNode(1);root.left new TreeNode(2);root.right new TreeNode(3);root.left.left new TreeNode(4);tree2Str606 solution new tree2Str606();String res solution.tree2str(root);System.out.print(res );}小白您好面试官这回可以了吧我终于有钱请小美看电影了 更多算法题解请看 面试数据结构与算法总结分类leetcode目录【基础版】
编码道路漫漫只要先看脚下的路徐徐前进即可。
