题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是将二叉树用字符串表现，规则是对于一个节点的左右子节点用（）包裹，空节点就是（），同时注意省略无意义的（），比如右节点空就能省略。

思路分享

  • 官方题解镇楼

    https://leetcode.cn/problems/construct-string-from-binary-tree/solutions/1343920/gen-ju-er-cha-shu-chuang-jian-zi-fu-chua-e1af/

  • 先分析这个括号是怎么加的，本质上，一个子节点对应一个括号，所以递归上来的加一个括号就行，这样也不违反最外面无括号的规律。同时多余的括号就两种情况，第一种是两个子树都是空，也就是叶子节点；第二种是左子树非空，右子树为空就能去掉右子树。

  • 总结规律，发现无论什么情况，只要右子树为空就能去掉，而左子树得是右子树为空再根据自己是空才去掉。于是本题的逻辑就清楚了。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def tree2str(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ""
        left = "(" + self.tree2str(root.left) + ")"
        right = "(" + self.tree2str(root.right) + ")"
        if right == "()":
            right = ""
            if left == "()":
                left = ""
        return str(root.val) + left + right