LeetCode 606 Construct String from Binary Tree

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

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

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

例 :

给予树:

     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.

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

查看所有标签

猜你喜欢:

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

自制编译器

自制编译器

[日] 青木峰郎 / 严圣逸、绝云 / 人民邮电出版社 / 2016-6 / 99.00元

本书将带领读者从头开始制作一门语言的编译器。笔者特意为本书设计了CЬ语言,CЬ可以说是C语言的子集,实现了包括指针运算等在内的C语言的主要部分。本书所实现的编译器就是C Ь语言的编译器, 是实实在在的编译器,而非有诸多限制的玩具。另外,除编译器之外,本书对以编译器为中心的编程语言的运行环境,即编译器、汇编器、链接器、硬件、运行时环境等都有所提及,介绍了程序运行的所有环节。一起来看看 《自制编译器》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

html转js在线工具
html转js在线工具

html转js在线工具