验证二叉树
双层递归（时间复杂度高）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool result = true; //第一层递归判断是否是二叉搜索树 void judge_tree(TreeNode* cur ) { if(cur==nullptr) return; if (cur->left!=nullptr ) Traversal(cur->left , cur->val ,1); if (cur->right!=nullptr ) Traversal(cur->right , cur->val ,2); judge_tree(cur->left ); judge_tree(cur->right ); } //第二层递归判断左右子树是不是都小于自己或都大于自己 void Traversal(TreeNode* cur , int root_val , int flag) { if(cur==nullptr) return; if(flag == 1) { if(cur->val >= root_val) result=false; } if(flag == 2) { if(cur->val <= root_val) result=false; } Traversal(cur->left , root_val , flag); Traversal(cur->right , root_val ,flag); } bool isValidBST(TreeNode* root) { if(root == nullptr) return false; judge_tree(root ); return result; } };
单层递归
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: //记录上一个点 TreeNode* pre = nullptr; bool judge_tree(TreeNode* cur) { if(cur==nullptr) return true; bool left_val = judge_tree(cur->left); //当前点应该比上一个大，如果小发生错误 if(pre != nullptr && cur->val <= pre->val) return false; //更新当前点 pre = cur; bool right_val = judge_tree(cur->right); return left_val&right_val; } bool isValidBST(TreeNode* root) { if(root==nullptr) return true; return judge_tree(root); } };
二刷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: long pre_num = LONG_MIN; bool result = true; bool track_back(TreeNode* cur) { if(cur == nullptr ) return result; bool left_falg = track_back(cur->left); if(cur->val <= pre_num ) result = false; pre_num = cur->val; bool right_flag = track_back(cur->right); return result; } bool isValidBST(TreeNode* root) { if(root == nullptr ) return true; else if(root->left==nullptr && root->right == nullptr) return true; return track_back(root); } };
