DFS基础问题-LeetCode 98、101（二叉树中序遍历，层次遍历）
DFS基础问题-LeetCode 98、101（二叉树中序遍历，层次遍历）
作者：TeddyZhang，公众号：算法工程师之路
DFS基础问题：LeetCode #98 #101
1
编程题
【LeetCode #98】验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
示例 1: 输入: 2 / \ 1 3 输出: true
示例 2: 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。
解题思路：
如何判断一棵二叉树是否为BST，很简单的思路就是：对这棵二叉树进行中序遍历，然后判断其中序遍历后的序列是不是单调递增的序列，如果是，则为一棵BST，否则不是。
但是二叉树的中序遍历有两个版本，递归版和非递归版本，我们先来看递归版本，其实际就是一个dfs算法，从根节点依次向下深入，在递归体内我们需要设置两个变量min, max来进行数值边界的判断，以使得遍历后的序列为一个单调增序列！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode* root, long int mi, long int ma){
if(root == nullptr){
return true;
}
if(root->val <= mi || root->val >= ma) return false;
else return dfs(root->left, mi, root->val) && dfs(root->right, root->val, ma);
}
bool isValidBST(TreeNode* root) {
if(root == NULL) return true;
return dfs(root, INT64_MIN, INT64_MAX);
}
};
我们还可以使用一个堆栈来实现二叉树的费递归版的中序遍历！！！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root == nullptr) return true;
TreeNode* pre = nullptr;
TreeNode* cur = root;
stack<TreeNode*> sta;
while(!sta.empty() || cur != nullptr){
if(cur != nullptr){
sta.push(cur);
cur = cur->left;
}else{
cur = sta.top();
sta.pop();
if(pre && cur->val <= pre->val) return false;
pre = cur;
cur = cur->right;
}
}
return true;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
【LeetCode #101】对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3
解题思路：
对称二叉树，很明显我们需要使用层次遍历，同样的，我们使用递归和非递归两种方法来解决这个问题，通常递归的方法都要简单一些，但是在大的工程项目中一般不使用递归（出错不容易分析）。层次遍历我们使用队列结构！
注意递归版本的递归退出条件，如果两者都为空，则说明到达了叶节点，返回true. 如果只有一个为空，直接返回false, 因为这种条件下无法比较！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode* l, TreeNode* r){
if(l == nullptr && r == nullptr){
return true;
}
if(l == nullptr || r == nullptr){
return false;
}
if (l->val == r->val){
return dfs(l->left, r->right) && dfs(l->right, r->left);
}
return false;
}
bool isSymmetric(TreeNode* root) {
return dfs(root, root);
}
};
当然层次遍历也是有非递归版本的，我们可以使用一个size遍历来一次处理一层数据，由于一层数据是相对于中心对称的，因此我们可以分别使用一个堆和一个栈结构来处理！当然了使用数组也没有问题的啦！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root == nullptr) return true;
queue<TreeNode*> que;
queue<int> q;
stack<int> p;
que.push(root);
while(!que.empty()){
int size = que.size();
while(size--){
TreeNode* tmp = que.front();
que.pop();
if(tmp->left != nullptr){
q.push(tmp->left->val);
p.push(tmp->left->val);
que.push(tmp->left);
}else{
q.push(-1); // 后面判断时使用
p.push(-1);
}
if(tmp->right != nullptr){
q.push(tmp->right->val);
p.push(tmp->right->val);
que.push(tmp->right);
}else{
q.push(-1);
p.push(-1);
}
}
while(!p.empty()){
if(p.top() == q.front()){
p.pop(); q.pop();
}else{
return false;
}
}
}
return true;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/symmetric-tree
完