【刷题笔记】LeetCode 606. Construct String from Binary Tree

佚名 5年前 (2019-05-23) 算法 1654人围观抢沙发百度已收录

题意

给一棵二叉树，把它转化为字符串返回。转化字符串的要求如下：

1. null 直接转化为 () ;（这个要求其实有点误导人~）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

2. 子节点用 () 包裹起来；（这是我自己根据例子添加的要求）

3. 省略所有不影响二叉树与字符串之间一对一关系的 () ;

做题链接

代码

//JavaScript
var tree2str = function(t) {
    if(t === null) return '';
    if(t.left === null && t.right === null) return ''+t.val;
    return '' + t.val + '(' + tree2str(t.left) + ')' + (t.right === null ? '' : '(' + tree2str(t.right) + ')');
};

简单的二叉树题目，一般我都期待能用简单的递归完成。

这道题起初我把问题想得太复杂，以为需要一个辅助函数。分析例子和答案之后才发现其实不用。

三种情况

三种情况分别对应上面三行代码

情况一：

if(t === null) return '';

这种情况究竟需要 return ''; 还是 return '()'; 呢？

上面说过，LeetCode原题的描述有点误导人。

我自己的分析是： () 是父节点用来包裹子节点，以区分层级关系的。所以如果用递归，需要包裹括号的时候，也应该由父节点来执行包裹这个动作，不然不好分析，而且需要额外处理特殊情况。所以最好还是 return '';

情况二：

if(t.left === null && t.right === null) return ''+t.val;

这个情况相对简单，因为前面我们分析过了，最好由父节点来执行包裹括号的操作，所以这里我们的逻辑就比较简明。

情况三：

//当节点 t 不为 null，且它至少有一个子节点不为 null
return '' + t.val + '(' + tree2str(t.left) + ')' + (t.right === null ? '' : '(' + tree2str(t.right) + ')');

这种情况相对烧脑。因为题目的误导，一开始我想的很深，结果做出来，发现没有那么复杂。

例如上面的对应字符串为： "1(2(4(6)))(3()(5(7)))" 。

做出来之后重新分析了一下，发现其实是这样的：

1. 一个 () 只包裹一个子树，所以其实当右子树是 null 的时候，可以直接省略掉右子树字符串（不会影响整体布局），当然左子树为 null 的时候不一定可以。

2. 在第三种情况下， '(' + tree2str(t.left) + ')' 一定需要调用，为什么呢？因为如果左子树为 null ，则证明右子树不为 null （因为第三种情况是至少有一个子树不为 null ），在这种情况下，左子树一定要有一个空括号来占一个位置，才不会影响树的整体布局；而当左子树不为 null 时，废话不多说，当然要调用。

PS：英文分析链接