深搜和广搜问题-LeetCode 110、104（DFS, BFS）
深搜和广搜问题-LeetCode 110、104（DFS, BFS）
编程题
【LeetCode #104】二叉树的最大深度
给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
解题思路： 二叉树的最大深度，这个问题在剑指Offer中也出现过，今天我们通过DFS和BFS两种方式来重新复习一下这个问题。
DFS算法： 我们使用栈结构来储存每个节点root以及该节点的深度deep，由于对tuple的使用还不太熟练，需要多练习，一次使用tuple来讲树结构体指针和对应的整型变量深度。从根节点开始遍历，首先一直遍历左子节点，并将节点压入栈中，如果左子节点为空，则从栈中弹出，并开始遍历弹出节点的右子节点。这个过程也就相当于回溯了，回到上一级去。
/**
* 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:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
stack<tuple<TreeNode*, int>> sta;
int maxdeep = 0;
int deep = 0;
while(!sta.empty() || root){
while(root){
sta.push(make_tuple(root, deep+1));
deep++;
root = root->left;
}
tie(root, deep) = sta.top();
if(maxdeep < deep) maxdeep = deep;
sta.pop();
root = root->right;
}
return maxdeep;
}
};BFS算法: 这个其实质就是层次遍历，使用队列来储存树节点，并使用size变量记录每次节点的数量，在一次循环中，处理掉一层的节点，具体做法：将某一层所有节点的子节点压入队列后，并将所有的节点移除队列。 在处理某一层的树节点的同时，使用count变量记录处理的层数。即为最大深度！
/**
* 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:
int maxDepth(TreeNode* root) {
if(root == nullptr){
return 0;
}
queue<TreeNode*> que;
que.push(root);
int count = 0;
while(que.size() != 0){
int size = que.size();
while(size--){
TreeNode* tmp = que.front();
if(tmp->left != nullptr) que.push(tmp->left);
if(tmp->right != nullptr) que.push(tmp->right);
que.pop();
}
count++;
}
return count;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
【LeetCode #110】平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1: 给定二叉树 [3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回 true 。
解题思路： 对于平衡树来说，其要求是左右子树的深度之差不能大于1，我们使用一个简单的递归思路来解决，当然也可以使用非递归，不过比较复杂！
由于我们需要知道左右子树的深度，那么递归的返回值显然是左右子树的深度，但我们整个主函数是返回一个bool, 因此我们将bool变量flag设置为类中的成员变量，通过递归函数对其值进行更新。
/**
* 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 res = true;
int check(TreeNode* node){
if(node == nullptr) return 0;
int l = 1 + check(node->left);
int r = 1 + check(node->right);
if(abs(l-r) > 1){
res = false;
}
return max(l, r);
}
bool isBalanced(TreeNode* root) {
check(root);
return res;
}
};