Leetcode 331.Verify Preorder Serialization of a Binary Tree

xindoo

发布于 2021-01-22 12:48:55

3910

发布于 2021-01-22 12:48:55

Verify Preorder Serialization of a Binary Tree不算一道特别复杂的题目。题意大概是这样的：给你一个字符数组，让你判断这个数组中的值是不是一棵二叉树的先序遍历结果，其中'#'节点是空节点，无左右字节点。原文中举了一个例子。 "9,3,4,#,#,1,#,#,2,#,6,#,#" 就是下面这棵二叉树的先序遍历结果。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

　　可能很多人第一眼看到题目就开始如何思考根据已知的先序遍历结果去构建一棵二叉树，这样确实是可以解决这道题，但会变得比较复杂。其实完全不需要重新建一棵树，我们来找找规律。　　仔细看看题目中给的例子，如果一层有x个非'#'节点，那么下一层应该有多少节点，你可以自己再画两棵来验证下，我相信你肯定知道怎么做了。下面放出我的java代码，仅供参考。最近在转Java开发，发现java很多自带的库还是很实用的。

public class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] str = preorder.split(",");
        int len = str.length;
        int nextlen = 1;
        int pos = 0;
        while (true) {
            int cnt = 0;
            for (int i = pos; i < pos+nextlen && i < len; i++) {
                if (!str[i].equals("#"))
                    cnt++;
            }
            pos += nextlen;
            nextlen = cnt*2;
            if (0 == nextlen)    //代表下层无节点，挑出循环。 
                break;
        }
        if (pos == len)
            return true;
        else
            return false;
    }
}

　　讲解下我代码的思路，我先用字符串的split函数将输入分割成字符数组，然后用nextlen来保存当前遍历过程中的下层应该有多少个节点。 cnt来计数当前遍历的一层非#节点的个数，那么下层的节点数应该是2*cnt。pos遍历保存当前遍历的下表。如果这是一个合法二叉树的先序遍历次序，那么最终pos的值正好等于字符数组的长度。

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

原始发表：2016-03-08，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树