1.BST树区间元素搜索问题

//寻找元素值在区间[i,j]的元素
//对于BST树而言，中序遍历由小到大排列
void findvalues(Node* root,vector&vec,int i,intj)
{if(root != nullptr){if(root->data > i){ findvalues(root->left,vec,i,j);}if(root->data >= i  && root->data <= j){vec.push_back(root->data);}if(root->data < j){findvalues(root->right,vec,i,j);}}
}

2. 判断一颗二叉树是不是BST树

思路：利用BST树中序遍历是一个升序的特点

bool isBSTree(Node* root,Node*& pre)
{if(node == nullptr){return true;}  //左子树if(!isBSTree(root->left,pre)){return false;}if(pre != nullptr && root->data < pre->data)        {return false;}pre = root;//右子树return isBSTree(root->right,pre);
}

3.判断BST树子树问题

bool isChildTree(Node* childroot)
{if(childroot == nullptr){return false;}Node* cur = childroot;while(cur!=nullptr){if(cur->data == childroot->data){break;}else if(cur->data < childroot->data){cur = cur->right;}else{cur = cur->left;}}if(cur != nullptr){return isChildTree(cur,childroot); }return false;
}bool isChildTress(Node* parent,Node* childroot)
{if(child == nullptr){return true;}if(parent == nullptr || parent->data != childroot->data ){return false;}return isChildTree(parent->left,childroot->left) && isChildTree(parent->right,childroot->right);
}

4.BST树最近公共祖先

TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q)
{if(root == nullptr){return nullptr;}if(root->data < p->data && root->data < q->data){return lowestCommonAncestor(root->right,p,q);}else if(root->data > p->data && root->data > q->data){return lowestCommonAncestor(root->left,p,q);}else{return root;}return nullptr;
}

5.二叉树镜像对称问题

TreeNode* mirrorTree(TreeNode* root)
{if(root == nullptr){return nullptr;}TreeNode* tmp = root->left;root->left = root->right;root->right = tmp;mirrorTree(root->left);mirrorTree(root->right);return root;
}

6.对称的二叉树

bool isSymmetric(TreeNode* root) 
{if(root == nullptr){return true;}return isSymmetric(root->left,root->right);
}bool isSymmetric(TreeNode* node1,TreeNode* node2)
{if(node1 == nullptr && node2 == nulpptr){return true;}if(node1 == nullptr || node2 == nullptr){return false;}if(node1->val != node2->val){return false; }return isSymmeric(node1->left,node2->right) && isSymmeric(node1->right,node2->left);
}

7.根据前序遍历和后续遍历的序列重建二叉树

TreeNode* bulidTree(vector &perorder,vector &inorder)
{return rebulid(peroder,0,peroder.size()-1,inorder,0,inorder.size()-1);   
}TreeNode* rebuild(vector& perorder,int i,int j,vector& inorder,int m,int n)
{if(i>j || m>n){return nullptr;} //创建根节点，先序遍历的第一个结点就是根结点TreeNode* node = new TreNode(perorder[i]);for(int k = m;k<=n;++k){if(inorder[k] == perorder[i]){  //左子树node->left = rebulid(perorder,i+1,i+k-m,inorder,m,k-1);//右子树node->right = rebulid(perorder,i+k-m+1,j,inorder,k+1,n);return node;}}return node;
}

8.判断二叉树是不是平衡树

bool balance(TreeNode* root)
{if(root == nullptr){return true;}int h = 0;bool flag = true;balance(root,h,true);return flag;
}int balance(TreeNode* node,int h,bool & flag)
{if(node == nullptr){return h;}//左子树int left = balance(node->left,h+1,flag);if(!flag){return 0;}//右子树int right = balance(node->right,h+1,flag);if(!flag){return 0; }     if(abs(left-right) > 1)  //高度差大于1，失衡{flag = false;}return max(left,right);
}

9.BST树的第K大结点

中序遍历由小大排列，LVR

RVL，第K个元素就是第K大结点

int i = 0;
int KthLargest(TreeNode* root,int k)
{return getVal(root,k)->val;
}TreeNode* getVal(TreeNode* node,int k)
{if(node == nullptr){return nullptr;}//RTreeNode* right = getVal(node->right,k);if(right != nullptr){return right; }if(++i == k)     //V{return node;}//Lreturn getVal(node->left,k);
}