AI工具人
提示词工程师

Leetcode 331.Verify Preorder Serialization of a Binary Tree

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的值正好等于字符数组的长度。

赞(0) 打赏
未经允许不得转载:XINDOO » Leetcode 331.Verify Preorder Serialization of a Binary Tree

评论 3

  1. #1

    I have noticed you don’t monetize your site, don’t waste your traffic, you can earn extra bucks every month because you’ve got hi
    quality content. If you want to know how to make extra money, search for: Mrdalekjd methods for $$$

    FirstGabriel7年前 (2017-09-25)回复
  2. #2

    This is a really good tip particularly to those new to the blogosphere.
    Short but very accurate information… Thanks for sharing this
    one. A must read post!

    video games help adhd5年前 (2019-02-12)回复
    • It’s typical for me at least to be enjoying properly all night or nights and
      instantly several loss holding two terrible cards
      calls my big increase with nobleman or bullets.

      Kelli5年前 (2019-02-26)回复

觉得文章有用就打赏一下文章作者

非常感谢你的打赏,我们将继续给力更多优质内容,让我们一起创建更加美好的网络世界!

支付宝扫一扫打赏

微信扫一扫打赏

登录

找回密码

注册