LeetCode 606 Construct String from Binary Tree

栏目: 数据库 · 发布时间: 6年前

内容简介：给予一颗二叉树，根据前序遍历构建一个字符串, 不过需要在每个元素和他的子元素的外层用例 :采用深度优先遍历, 需要注意特殊情况: 当一个节点有左子树, 但没有右子树时, 可以省略右子树的

给予一颗二叉树，根据前序遍历构建一个字符串, 不过需要在每个元素和他的子元素的外层用 () 包住, 并且需要你不会影响字符串和原始二叉树之间一一对应关系的空括号对.

例 :

给予树：

     1
   /   \
  2     3
 /
4

全部返回应该是: `1(2(4)())(3()())`.
省略掉不必要的括号对后的结果为: `1(2(4))(3)`.


给予树：
     1
   /   \
  2     3
   \  
    4 

返回: "1(2()(4))(3)"

解法

采用深度优先遍历, 需要注意特殊情况: 当一个节点有左子树, 但没有右子树时, 可以省略右子树的 () . 当一个节点有右子树, 但没有左子树, 就不能省略左子树的 () .

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public String tree2str(TreeNode t) {
        if (t == null) {
            return "";
        }
        if (t.left == null && t.right == null) {
            return t.val + "";
        } else if (t.left != null && t.right != null) {
            return t.val + "(" + tree2str(t.left) + ")" + "(" + tree2str(t.right) + ")";
        } else if (t.left != null) {
            return t.val + "(" + tree2str(t.left) + ")";
        } else {
            return t.val + "()(" + tree2str(t.right) + ")";
        }
    }
}

Runtime: 6 ms, faster than 84.71% of Java online submissions for Construct String from Binary Tree. Memory Usage: 37.6 MB, less than 98.36% of Java online submissions for Construct String from Binary Tree.

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

信息检索导论

Christopher D.Manning、Hinrich Schütze、Prabhakar Raghavan / 王斌 / 人民邮电出版社 / 201008 / 69.00元

封面图片为英国伯明翰塞尔福瑞吉百货大楼，其极具线条感的轮廓外型优美，犹如水波的流动。其外表悬挂了1.5万个铝碟，创造出一种极具现代气息的纹理装饰效果，有如夜空下水流的波光粼粼，闪烁于月光之下，使建筑的商业氛围表现到极致。设计该建筑的英国“未来系统建筑事物所”，将商场内部围合成一个顶部采光的中庭，配以交叉的自动扶梯，使购物环境呈现出一种凝聚的向心力和商业广告的展示效应。作为英国第二商业城市伯明翰的建......一起来看看《信息检索导论》这本书的介绍吧!

码农工具

html转js在线工具

RGB CMYK 转换工具

RGB CMYK 互转工具