leetcode331. Verify Preorder Serialization of a Bi

weapon 发布于2019-08-16 13:50 / 581人阅读

摘要：如果我们从右往左看先序遍历，就知道后两个节点如果遇到第三个节点，则该节点就应当是这两个节点的父节点。如果在遍历的过程中根节点数量小于，则说明这棵树有问题。而如果遍历结束之后，剩下的根节点数不等于，也说明这个先序遍历存在问题。

题目要求

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node"s value. If it is a null node, we record using a sentinel value such as #.

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

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character "#" representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
Example 2:

Input: "1,#"
Output: false
Example 3:

Input: "9,#,#,1"
Output: false

思路和代码

我们知道，任何两个节点都可以和位于左边的非叶节点构成一棵有三个节点的树。如果我们从右往左看先序遍历，就知道后两个节点如果遇到第三个节点，则该节点就应当是这两个节点的父节点。我们可以将每一个#看做一个根节点，每遇到#就将记录的根节点数加一，当遇到数字时，则代表该数字应当能够和两个节点构成新的树，并且该数字成为新的根节点，因此需要将根节点数量减一。如果在遍历的过程中根节点数量小于1，则说明这棵树有问题。而如果遍历结束之后，剩下的根节点数不等于1，也说明这个先序遍历存在问题。

    public boolean isValidSerialization(String preorder) {
        if(preorder==null) return false;
        if(preorder.length() == 0) return true;
        String[] nodes = preorder.split(",");
        int nodeCount = 0;
        for(int i = nodes.length - 1; i >= 0 ; i--) {
            if(nodes[i].equals("#")) {
                nodeCount++;
            } else {
                nodeCount--;
            }
            if(nodeCount <= 0) return false;
        }
        return nodeCount == 1;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

服务器托管云服务器 Preorder Serialization verify automation of com

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72418.html

LeetCode 331. Verify Preorder Serialization of a B

摘要：如果它是一个空节点，我们可以使用一个标记值记录，例如。例如，上面的二叉树可以被序列化为字符串，其中代表一个空节点。每个以逗号分隔的字符或为一个整数或为一个表示指针的。如果满足前序遍历，那么最后栈中有且仅有一个元素，且是。 Description One way to serialize a binary tree is to use pre-order traversal. When ...

张巨伟 2019-07-31 10:10 评论0 收藏0
Verify Preorder Serialization of a Binary Tree

摘要：令，那么从累加会一直保持正，最后为。从左往右比较好理解，因为总是总到左再到右，的总是的，所以一定是保持。注意从开始，因为没有。 Verify Preorder Serialization of a Binary Tree 题目链接：https://leetcode.com/problems... recursion，用个全局的index： public class Solution {...

melody_lql 2019-08-14 17:23 评论0 收藏0
leetcode449. Serialize and Deserialize BST

摘要：题目要求将二叉搜索树序列化和反序列化，序列化是指将树用字符串的形式表示，反序列化是指将字符串形式的树还原成原来的样子。假如二叉搜索树的节点较多，该算法将会占用大量的额外空间。题目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...

Honwhy 2019-08-16 16:58 评论0 收藏0
[Leetcode] Verify Preorder Sequence in Binary Sear

摘要：如果继续降序，说明又向左走了，这样等到下次向右走得时候也要再次更新最小值。这样，序列无效的条件就是违反了这个最小值的限定。我们同样可以用本题的方法解，不过是从数组的后面向前面遍历，因为在后面了。栈的增长方向也是从高向低了。 Verify Preorder Sequence in Binary Search Tree Given an array of numbers, verify ...

未东兴 2019-08-14 12:46 评论0 收藏0
Serialize and Deserialize Binary Tree & BST

摘要：思路理论上说所有遍历的方法都可以。但是为了使和的过程都尽量最简单，是不错的选择。用作为分隔符，来表示。复杂度代码思路这道题和之前不同，一般的树变成了，而且要求是。还是可以用，还是需要分隔符，但是就不需要保存了。 297. Serialize and Deserialize Binary Tree Serialization is the process of converting a...

eccozhou 2019-08-14 17:11 评论0 收藏0