我在這個(gè)問題上犯了個(gè)錯(cuò)誤，一開始我僅僅把二叉樹三個(gè)節(jié)點(diǎn)對(duì)比大小，可能造成二叉樹局部三個(gè)節(jié)點(diǎn)符合BST樹特性，但是放在全局就不符合了。因此我們要記錄min_node和max_node，從頂層遞歸到下層。而不是從下層開始，僅僅因?yàn)槿齻€(gè)節(jié)點(diǎn)滿足就返回true。
典型情況：
10 / / 4 15 / / / /2 5 6 17如上圖，15，6，17局部滿足BST樹，但是6<10，所以不是BST樹。
我的錯(cuò)誤解法：
class Solution {public: bool isValidBST(TreeNode* root) { return root != NULL ? is_bst(root) : true; } bool is_bst(TreeNode* root){ if(root->left == NULL && root->right == NULL) return true; else if(root->left == NULL) return is_bst(root->right); else if(root->right == NULL) return is_bst(root->left); else return is_bst(root->left) && is_bst(root->right) && (root->left->val <= root->val && root->right->val > root->val); }};實(shí)際上錯(cuò)誤解法通過了80%的case。
下面說正確解法。方法一： 利用BST樹的特性，從上往下遞歸，記錄min_node和max_node，對(duì)左子樹來說，只需記錄max_node，即它的父節(jié)點(diǎn)；同理對(duì)于右字?jǐn)?shù)，只需記錄min_node。然后它們滿足BST關(guān)系即可。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool isValidBST(TreeNode* root) { return root != NULL ? is_bst(root, NULL, NULL) : true; } bool is_bst(TreeNode* root, TreeNode* min_node, TreeNode* max_node){ if(root == NULL) return true; if(min_node != NULL && root->val <= min_node->val || max_node != NULL && root->val >= max_node->val) return false; //if false, stop and return return is_bst(root->left, min_node, root) && is_bst(root->right, root, max_node); }};方法二：利用中序遍歷關(guān)系。由于BST樹的中序遍歷是有序的，所以我們用中序遍歷來做文章。
class Solution {public: bool isValidBST(TreeNode* root) { TreeNode* PRev = NULL; return is_bst(root, prev); } bool is_bst(TreeNode* root, TreeNode*& prev){ if(root == NULL) return true; if(!is_bst(root->left, prev)) return false; if(prev != NULL && prev->val >= root->val) return false; prev = root; return is_bst(root->right, prev); }};利用prev節(jié)點(diǎn)一開始為NULL，后來作為中序遍歷的前一個(gè)節(jié)點(diǎn)，和當(dāng)前節(jié)點(diǎn)進(jìn)行比較判斷是否滿足BST特性即可。
唉，人生苦短，我用Python :)
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def isValidBST(self, root): self.prev = None return self.is_bst(root, self.prev) def is_bst(self, root, prev): if root == None: return True if not self.is_bst(root.left, self.prev): return False if self.prev != None and self.prev.val >= root.val: return False self.prev = root return self.is_bst(root.right, self.prev)新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
