树专题
LC98验证二叉搜索树
1.分析 2.代码
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/
1 3
输出: true
image.png
即我们从顶向下进行分析每个数据的取值范围，如上图所示。我们就可以递归下去，每个左右子树的取值范围都只和根节点的数据范围相关。
class Solution {
public:
bool isValidBST(TreeNode* root) {
return dfs(root,INT_MIN,INT_MAX);
}
bool dfs(TreeNode* root,long long mmin,long long mmax)//传入LONG类型
{
if(!root) return true;//当前子树为空，一定可以满足条件，返回TRUE
if(root->val<mmin||root->val>mmax) return false; //先判根节点是不是满足，不合法
//若根节点满足，则考虑左右子树是否满足，用递归，找到合适的区间范围
return dfs(root->left,mmin,root->val-1ll)&&dfs(root->right,root->val+1ll,mmax);//1ll指value负无穷溢出，所以用LL
}
};
LC94 二叉树的中序遍历
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
2
/
3
输出: [1,3,2]
1、分析 采用迭代算法
采用非递归方法完成。即需要一个栈来模拟整个过程。先把整个树压栈，即把树的最左边那一条链上的节点都压入栈，再依次从栈顶弹出元素，每次判断一下此节点是否有右子树，若有则把右子树整个压栈，而把整个右子树压栈的动作就是和最初把整个树压栈一样。
写递归其实是系统开栈帮助我们模拟。
我们自己用栈来模拟，先把最左边的链全部放入栈中，若没有右子树，就回到上一层，中序就是遍历了跟之后遍历右子树，迭代很常见在树中，前序遍历和后序遍历是完全对称的。
class Solution {
public:
vector<int> ans;
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;//定义一个栈
if(!root) return ans;//
while(root||s.size())//不为空
{
while(root) //把树的最左边一条链上的节点压栈
{
s.push(root);
root=root->left;
}
auto p=s.top(); //取出栈顶元素
ans.push_back(p->val);
s.pop();
root=p->right; //让此栈顶元素的整个右子树压栈
}
return ans;
}
