900. Closest Binary Search Tree Value(easy)
class Solution {public:/*** @param root: the given BST* @param target: the given target* @return: the value in the BST that is closest to the target*/int closestValue(TreeNode * root, double target) {// write your code here// if (root == NULL){// return// }TreeNode * temp = root;float diff = INT_MAX;int res = 0;while(temp != NULL){if (abs(temp -> val - target) < diff){diff = abs(temp -> val - target);res = temp -> val;}if (temp -> val > target){temp = temp -> left;}else{temp = temp -> right;}}return res;}};
596. Minimum Subtree(递归)
class Solution {
public:
/**
* @param root: the root of binary tree
* @return: the root of the minimum subtree
*/
TreeNode * findSubtree(TreeNode * root) {
// write your code here
helper(root);
return RootRes;
}
int helper(TreeNode * root){
if (root == NULL){
return 0;
}
int left = helper(root -> left);
int right = helper(root -> right);
if (left + right + root -> val < res){
res = left + right + root -> val;
RootRes = root;
}
return left + right + root -> val;
}
private:
int res = INT_MAX;
TreeNode * RootRes;
};
480. Binary Tree Paths（递归，DFS）
class Solution {
public:
/**
* @param root: the root of the binary tree
* @return: all root-to-leaf paths
*/
vector<string> binaryTreePaths(TreeNode * root) {
// write your code here
string temp = "";
vector <string> result;
if (root == NULL){
return result;
}
helper(root, temp, result);
return result;
}
void helper(TreeNode * root, string temp, vector<string>& result){
if (root -> left == NULL && root -> right == NULL){
temp += to_string(root -> val);
result.push_back(temp);
return;
}
temp = temp + to_string(root -> val) + "->";
//int length = temp.size();
if (root -> left != NULL){
helper(root -> left, temp, result);
//temp.substr(0, length);
}
if (root -> right != NULL){
helper (root -> right, temp, result);
//temp.substr(0, length);
}
}
};
453. Flatten Binary Tree to Linked List（后序遍历）
class Solution {
public:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
void flatten(TreeNode * root) {
// write your code here
if (root == NULL){
return;
}
if (root -> left){
TreeNode* temp = root -> left;
while(temp -> right != NULL){
temp = temp-> right;
}
temp -> right = root -> right;
root -> right = root -> left;
root -> left = NULL;
}
flatten(root -> right);
}
};
new:
class Solution {
public:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
void flatten(TreeNode * root) {
// write your code here
if (root == NULL){
return;
}
flatten(root -> left);
flatten(root -> right);
if (root -> left != NULL){
TreeNode * temp = root -> left;
while(temp -> right != NULL){
temp = temp -> right;
}
temp -> right = root -> right;
root -> right = root -> left;
root -> left = NULL;
}
}
};
93. Balanced Binary Tree(自低向上遍历)
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
bool isBalanced(TreeNode * root) {
// write your code here
return helper(root) != -1;
}
int helper(TreeNode * root){
if (root == NULL){
return 0;
}
int left = helper(root -> left);
int right = helper(root -> right);
if (left == -1 || right == -1 || abs(left - right) > 1){
return -1;
}else{
return max(left, right) + 1;
}
}
};
902. Kth Smallest Element in a BST
递归写法
class Solution {
public:
/**
* @param root: the given BST
* @param k: the given k
* @return: the kth smallest element in BST
*/
int kthSmallest(TreeNode * root, int k) {
// write your code here
helper(0, root, k);
return res;
}
int helper(int index, TreeNode * root, int k){
if (isExist == true){
return 0;
}
int left = 0, right = 0;
if (root -> left != NULL){
left = helper(index, root -> left, k);
}
int Now = left + 1 + index;
if (Now == k){
isExist = true;
res = root -> val;
//return 1;
}
if (root -> right != NULL){
right = helper(Now, root -> right, k);
}
return left + right + 1;
}
private:
int res = INT_MIN;
bool isExist = false;
};
费递归写法
class Solution:
"""
@param root: the given BST
@param k: the given k
@return: the kth smallest element in BST
"""
def kthSmallest(self, root, k):
# use binary tree iterator
dummy = TreeNode(0)
dummy.right = root
stack = [dummy]
for i in range(k):
node = stack.pop()
if node.right:
node = node.right
while node:
stack.append(node)
node = node.left
if not stack:
return None
return stack[-1].val
95. Validate Binary Search Tree（递归非递归中序遍历）
递归写法
class Solution {
private:
TreeNode *lastNode = NULL;
public:
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
bool isValidBST(TreeNode *root) {
if (root == NULL) {
return true;
}
if (!isValidBST(root->left)) {
return false;
}
if (lastNode != NULL && lastNode->val >= root->val) {
return false;
}
lastNode = root;
return isValidBST(root->right);
}
};
费递归写法
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
bool isValidBST(TreeNode * root) {
// write your code here
if (root == NULL){
return true;
}
if (root -> val == INT_MIN){
return true;
}
int tempVal = INT_MIN;
TreeNode * dummy = new TreeNode(INT_MIN + 1);
stack <TreeNode *> stk;
dummy-> right = root;
TreeNode* tempTreeNode = dummy;
stk.push(dummy);
while(!stk.empty()){
TreeNode * temp = stk.top();
stk.pop();
if (tempVal >= temp -> val){
return false;
}
tempVal = temp -> val;
if(temp -> right != NULL){
temp = temp -> right;
while(temp!= NULL){
stk.push(temp);
temp = temp -> left;
}
}
}
return true;
}
};
578. Lowest Common Ancestor III
class Solution {
public:
/*
* @param root: The root of the binary tree.
* @param A: A TreeNode
* @param B: A TreeNode
* @return: Return the LCA of the two nodes.
*/
TreeNode * lowestCommonAncestor3(TreeNode * root, TreeNode * A, TreeNode * B) {
// write your code here
if (root == NULL){
return res;
}
helper(root, A, B);
return res;
}
pair<bool, bool> helper(TreeNode * root, TreeNode * A, TreeNode * B){
if (root == NULL){
return make_pair(false, false);
}
pair <bool, bool>left = helper(root -> left, A, B);
pair <bool, bool> right = helper(root -> right, A, B);
if ((left.first == true && left.second == true) || (right.first == true && right.second == true)){
return make_pair(true, true);
}
pair <bool, bool> temp;
temp.first = left.first || right.first || root -> val == A -> val;
temp.second = left.second || right.second || root -> val == B -> val;
if (temp.first == true && temp.second == true){
res = root;
return make_pair(true, true);
}
return make_pair(temp.first, temp.second);
}
private:
TreeNode * res = NULL;
};
Leetcode 230 Kth Smallest Element in a BST
中序遍历
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
helper(root, k);
return res;
}
void helper(TreeNode* root, int k){
if (root == NULL){
return;
}
helper(root-> left, k);
index ++;
if (index == k){
res = root -> val;
}
helper(root-> right, k);
}
private:
int res = INT_MAX;
int index = 0;
};
非递归写法，模板
void PreOrderLoop(TreeNode *root)
{
std::stack<TreeNode *> s;
TreeNode *cur, *top;
cur = root;
while (cur != NULL || !s.empty())
{
while (cur != NULL)
{
printf("%c ", cur->data);
s.push(cur);
cur = cur->left;
}
top = s.top();
s.pop();
cur = top->right;
}
}
Leetcode 235. Lowest Common Ancestor of a Binary Search Tree
s使用class 返回值
class resultType {
public:
int aExist, bExist;
TreeNode* exist;
resultType(bool a, bool b, TreeNode* existance) {
aExist = a;
bExist = b;
exist = existance;
}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
resultType result = helper(root, p, q);
if (result.exist != NULL){
return result.exist;
}
return NULL;
}
resultType helper(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL){
return resultType(false, false, NULL);
}
resultType resLeft = helper(root->left, p, q);
resultType resRight = helper(root->right, p, q);
bool pExist = resLeft.aExist || resRight.aExist || root == p;
bool qExist = resLeft.bExist || resRight.bExist || root == q;
//cout root -> val << pExist << qExist << endl;
TreeNode* existRoot;
if (resLeft.exist != NULL) {
existRoot = resLeft.exist;
}
else if (resRight.exist != NULL) {
existRoot = resRight.exist;
}
else if (pExist && qExist) {
existRoot = root;
}
resultType resultReturn(pExist, qExist, existRoot);
return resultReturn;
}
};
若有收获，就点个赞吧
0 人点赞
