LeetCode算法题-Construct String fro

2019-03-11 本文已影响18人程序员小川

这是悦乐书的第273次更新，第288篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第141题（顺位题号是606）。构造一个字符串，该字符串由二叉树中的括号和整数组成，并具有前序遍历方式。null节点需要用空括号对“（）”表示。并且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。例如：

输入：二叉树：[1,2,3,4]

输出：“1（2（4））（3）”

说明：原始字符串需要为“1（2（4）（））（3（）（））”，但是需要省略所有不必要的空括号对，所以是“1（2（4））（3）”。

输入：二叉树：[1,2,3，null，4]

输出：“1（2（）（4））（3）”

说明：与第一个示例几乎相同，但是不能省略第一个括号对来打破输入和输出之间的一对一映射关系。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

题目有两点要求，一是前序遍历二叉树，二是使用括号将节点值串起来。同时，对于第二点又可以细分为两种情况，一是如果节点本身没有左右子节点，就不必使用括号；二是如果节点本身的左子节点不为空，右子节点为空，那么我们需要省掉右子节点的括号，直接对其左子节点继续处理。

使用递归的方式，如果当前节点为空，直接返回空串；如果当前节点不存在左右子节点，直接返回当前节点值的字符串；如果当前节点的左子节点不为空，右子节点为空，直接返回当前节点值与其左子节点的后续递归结果，其中左子节点前后需用括号。

剩下就是正常的情况，先处理根节点的值，再处理左子树，使用括号包起来，最后处理右子树，同样使用括号包起来。

/**
 * 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) {
        String result = preOrder(t);
        return result;
    }

    public String preOrder(TreeNode t){
        if (t == null) {
            return "";
        }
        if (t.left == null && t.right == null) {
            return t.val+"";
        }
        if (t.right == null) {
            return t.val + "("+ preOrder(t.left)+")";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(t.val);
        String s = preOrder(t.left);
        sb.append("("+s+")");
        String s2 = preOrder(t.right);
        sb.append("("+s2+")");
        return sb.toString();
    }
}

03 第二种解法

我们可以把上面的写法简化下，在一个方法里面完成，并且去掉StringBuilder类操作字符串，直接使用连接符拼接。

/**
 * 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+"";
        }
        if (t.right == null) {
            return t.val + "("+ tree2str(t.left)+")";
        }
        return t.val + "("+tree2str(t.left)+ ")" + "(" + tree2str(t.right) + ")";
    }
}

04 第三种解法

我们也可以使用迭代的方式。使用迭代的方式，首先要借助栈，遍历的顺序为根节点，右子树，左子树，因为栈先进后出的特性，所以要先处理右子树，其次我们还需要考虑括号的拼接顺序问题。

如果直接使用前后括号拼接，会发现尾括号少了一部分，那么我们需要借助另外一个对象来判断什么时候该加尾部空格。对此，我们使用HashSet，存放已经访问过的节点，并且原先直接出栈的方法要换成获取栈顶的节点但是不出栈，只有都访问过了，才会出栈并追加尾部括号，另外一种特殊情况当前节点左子节点为空，右子节点不为空，直接追加一个空括号即可。

遍历完所有节点后，根据题目的要求，会发现字符串头部和尾部都多了一个单括号，所以要截取字符串，去掉头尾的单括号。

/**
 * 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+"";
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Set<TreeNode> visited = new HashSet<TreeNode>();
        String result = "";
        stack.push(t);
        while (!stack.isEmpty()) {
            TreeNode temp = stack.peek();
            if (visited.contains(temp)) {
                stack.pop();
                result += ")";
            } else {
                visited.add(temp);
                result += "(" + temp.val;
                if (temp.left == null && temp.right != null) {
                    result += "()";
                }
                if (temp.right != null) {
                    stack.push(temp.right);
                }
                if (temp.left != null) {
                    stack.push(temp.left);
                }
            }
        }
        return result.substring(1, result.length()-1);
    }
}

05 小结

算法专题目前已日更超过四个月，算法题文章141+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！