Flatten Binary Tree to Linked List
Total Accepted: 17814 Total
Submissions: 64054My Submissions
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode *root) {
dfs(root);
}
TreeNode *dfs(TreeNode *root){
if(root==NULL) return NULL;
TreeNode *left=root->left,*leftTail=dfs(root->left),
*right=root->right,*rightTail=dfs(root->right);
if(left) {
root->right=left,root->left=NULL;
if(right){
leftTail->right=right;
return rightTail;
}else{
return leftTail;
}
}else{//left child is null
if(right) return rightTail;
else return root;//left and right are null
}
}
};
Validate Binary Search Tree
Total Accepted: 16968 Total
Submissions: 66123My Submissions
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.
class Solution {
public:
bool isValidBST(TreeNode *root) {
if(root==NULL) return true;
Pr tmp;return dfs(root,tmp);
}
typedef pair<int,int> Pr;
bool dfs(TreeNode *root,Pr &pr){
assert(root!=NULL);
int _min=root->val,_max=root->val;
if(root->left) {
Pr p1;
if(!dfs(root->left,p1)) return false;
if(p1.second>=root->val) return false; //@@error: pair p1; p1->second should be p1.second.//@error:p1.second>root->val,should be >=
_min=min(_min,p1.first);
}
if(root->right) {
Pr p2;
if(!dfs(root->right,p2)) return false;
if(p2.first<=root->val) return false;
_max=max(_max,p2.second);
}
pr=Pr(_min,_max);
return true;
}
};
或者
为dfs(Node * root,int l,int r)//检验root是否在[l,r]范围内，不是则不合格
class Solution {
public:
#define MIN 0x80000000
#define MAX 0x7FFFFFFF
bool isValidBST(TreeNode *root) {
return dfs(root,MIN,MAX);
}
bool dfs(TreeNode *root,int l,int r){
if(root==NULL) return true;
int val=root->val;
if(val<l||val>r) return false;
return dfs(root->left,l,val-1)&&dfs(root->right,val+1,r);
}
};