LeetCode --- 98. Validate Binary Search Tree
タイトルリンク:Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
confused what "{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
この問題の要求は,二叉木が二叉探索木(BST)であるかどうかを検出することである.
名前の通り、各ノードの下に最大2つのサブノードがあるツリーです.また、検索を容易にするために、ツリーまたは空のツリー、または次の性質を持つツリーを検索します.
左サブツリーが空でない場合、左サブツリー上のすべてのノードの値はルートノードの値より小さい.
右サブツリーが空でない場合、右サブツリー上のすべてのノードの値はルートノードの値より大きい.
その左,右サブツリーもそれぞれ二叉探索ツリーである.
二叉探索ツリーには、中順遍歴が厳格に増加するという特徴があるので、一つの特性を利用して、一つの二叉ツリーが二叉探索ツリーであるかどうかを検査することができます.pre変数を使用して前のノードを記録し、ツリーを中順にループし、preノードの数が現在のノードより小さいかどうかを検出します.
時間複雑度:O(n)
空間複雑度:O(1)
転載は出典:LeetCode---98.Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
confused what "{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:
1
/ \
2 3
/
4
\
5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
この問題の要求は,二叉木が二叉探索木(BST)であるかどうかを検出することである.
名前の通り、各ノードの下に最大2つのサブノードがあるツリーです.また、検索を容易にするために、ツリーまたは空のツリー、または次の性質を持つツリーを検索します.
左サブツリーが空でない場合、左サブツリー上のすべてのノードの値はルートノードの値より小さい.
右サブツリーが空でない場合、右サブツリー上のすべてのノードの値はルートノードの値より大きい.
その左,右サブツリーもそれぞれ二叉探索ツリーである.
二叉探索ツリーには、中順遍歴が厳格に増加するという特徴があるので、一つの特性を利用して、一つの二叉ツリーが二叉探索ツリーであるかどうかを検査することができます.pre変数を使用して前のノードを記録し、ツリーを中順にループし、preノードの数が現在のノードより小さいかどうかを検出します.
時間複雑度:O(n)
空間複雑度:O(1)
1 class Solution
2 {
3 public:
4 bool isValidBST(TreeNode *root)
5 {
6 TreeNode *pre = NULL;
7 inorderTraversal(root, pre);
8 }
9 private:
10 bool inorderTraversal(TreeNode *p, TreeNode *&pre)
11 {
12 if(p == NULL)
13 return true;
14
15 if(!inorderTraversal(p -> left, pre))
16 return false;
17
18 if(pre != NULL && pre -> val >= p -> val)
19 return false;
20 pre = p;
21
22 if(!inorderTraversal(p -> right, pre))
23 return false;
24
25 return true;
26 }
27 };
転載は出典:LeetCode---98.Validate Binary Search Tree