LeetCode 606 Construct String from Binary Tree

一份执着✘

发布于 2019-12-30 17:00:00

4310

发布于 2019-12-30 17:00:00

文章被收录于专栏：赵俊的Java专栏赵俊的Java专栏

题意

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

例 :

给予树：

     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.

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树