104.二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
思路一：递归DFS
每个节点的最大深度等于其左右子树最大深度+1。
maxDepth(root)=max(maxDepth(root->left),maxDepth(root->right))+1
int maxDepth(TreeNode* root) {
if(!root)
return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
如果递归过深，会产生很多临时变量，导致栈溢出。所以如何将递归的DFS转为非递归？递归转为非递归通常用栈来实现。
思路二：非递归DFS
int maxDepth(TreeNode* root) {
if(!root)
return 0;
int mm=0;#最大深度
stack<pair<TreeNode*,int>> s;#记录每个节点的深度
s.push({root,1});
while(!s.empty())
{
pair<TreeNode*,int> t=s.top();
s.pop();
TreeNode* tmp=t.first;
int n=t.second;
if(n>mm)
mm=n;
if(tmp->left)
s.push({tmp->left,n+1});
if(tmp->right)
s.push({tmp->right,n+1});
}
return mm;
}
以上方法都是用DFS的方法，最直观的方法是对二叉树的每一层进行遍历，即二叉树的层序遍历，用的是BFS的方法，即使用队列其求解。
102.二叉树的层序遍历
BFS，广度/宽度优先。说白了就是从上到下，先把每一层遍历完之后再遍历一下一层。
层序遍历可以用DFS的方法实现，但是要保存每个节点的深度值，使用二元组 (node, level) 来表示状态。而BFS不用。
- 根元素入队
- 当队列非空时
- 求队列长度
- 该长度内节点为同一深度
- 下一级节点入队
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if(!root)
return result;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
vector<int> cur;
int l=q.size();
for(int i=0;i<l;i++)
{
TreeNode* tmp=q.front();
q.pop();
cur.push_back(tmp->val);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
result.push_back(cur);
}
return result;
}
98.验证二叉搜索树
二叉搜索树的左子树小于根节点，右子树大于根节点。它的左、右子树也分别为二叉搜索树。
思路一：中序遍历
因为二叉树的中序遍历为递增数列，所以只要判断中序遍历后是否递增。中序遍历：左-》中-》右。
bool isValidBST(TreeNode* root) {
vector<int> vec;
midorder(root,vec);
for(int i=0;i<vec.size()-1;i++)
{
if(vec[i]>=vec[i+1])
return false;
}
return true;
}
void midorder(TreeNode* root,vector<int>& vec)
{
if(!root)
return;
midorder(root->left,vec);
vec.push_back(root->val);
midorder(root->right,vec);
}
思路二：递归
错误思想：如果左右子树是二叉搜索树，且左子树根节点值小于中间节点，右子czz树根节点的值大于中间节点，则可以判断为BST。忽略了左右子树内的值与中间节点的大小比较。
左子树保存节点最大值，右子树保存节点最小值，与中间节点比较可以解决。
bool isValidBST(TreeNode* root) {
return isBST(root,LONG_MIN,LONG_MAX);
}
bool isBST(TreeNode* root,long mi,long ma)
{
if(!root)
return 1;
if((mi>=root->val)||(ma<=root->val))
return 0;
return isBST(root->left,mi,root->val) && isBST(root->right,root->val,ma);
}
最大值最小值的数据类型为长整型。
700.二叉搜索树查找
给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。
思路一：迭代
比较给定值与根节点的大小，小于根节点找左子树，大于根节点找右子树，直到子节点为空。
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* new_node=root;
while(new_node!=nullptr)
{
if(val==new_node->val)
return new_node;
if(val>new_node->val)
new_node=new_node->right;
else
new_node=new_node->left;
}
return nullptr;
}
思路二：递归
TreeNode* searchBST(TreeNode* root, int val) {
if(!root)
return nullptr;
if(val==root->val)
return root;
if(val>root->val)
return searchBST(root->right,val);
else
return searchBST(root->left,val);
}
思路二：递归
450.BST的删除
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤:
1.首先找到需要删除的节点；
2.如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
难点：如何提前一步搜索，删除节点。还要保持BTS的特性。
- 如果目标节点大于当前节点值，则去右子树中删除；
- 如果目标节点小于当前节点值，则去左子树中删除；
-
如果目标节点就是当前节点，分为以下三种情况：
1.其无左子：其右子顶替其位置，删除了该节点；
2.其无右子：其左子顶替其位置，删除了该节点；
3.其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
左右子节点都有.png
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root)
return root;
if(key==root->val)//找到目标节点
{
if(!root->right)
return root->left;//让左子树代替该节点
if(!root->left)
return root->right;//让右子树代替该节点
TreeNode* node = root->right;//左右子树都存在，左子树移接到右子树最左节点
while(node->left){
node=node->left;
}
node->left=root->left;//移花接木
root=root->right;//根节点变为右子树
}
if(key>root->val)
root->right=deleteNode(root->right, key);//目标节点在右子树
else
root->left=deleteNode(root->left, key);//目标节点在左子树
return root;
}
};
致谢：感谢知乎万字长文！二叉树入门和刷题看这篇就够了！和梁先生的帮助！
网友评论