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.

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

查看所有标签

猜你喜欢:

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

YC创业营: 硅谷顶级创业孵化器如何改变世界

YC创业营: 硅谷顶级创业孵化器如何改变世界

兰德尔·斯特罗斯 (Randall Stross) / 苏健 / 浙江人民出版社 / 2014-8-1 / CNY 52.90

在互联网创业成本日益降低、融资却越来越难的今天,硅谷的Y Combinator因何成为全世界创业者趋之若鹜的创业圣地?为什么25岁左右的青年最适合创业?创业者如何才能在遴选面试中脱颖而出?为什么YC特别看好那些主要由黑客组成的创业团队? YC真的歧视女性吗?如何想出能够赢得投资的新点子?创业者应该如何寻找联合创始人? 获准进入Y Combinator及其创业公司全程跟踪批量投资项目的第一人,......一起来看看 《YC创业营: 硅谷顶级创业孵化器如何改变世界》 这本书的介绍吧!

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具