DFS基础问题-LeetCode 98、101（二叉树中序遍历，层次遍历）
- 2019 年 10 月 4 日
- 笔记
作者：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
完
