2020-02-25 刷题 2（二叉树）
2020-02-25 本文已影响0人
nowherespyfly
104 二叉树的最大深度
比较容易写的是递归做法：
time: 92.98%, memory: 5.14%
/**
* 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) return 0;
int l = maxDepth(root -> left), r = maxDepth(root -> right);
int d = l > r ? l : r;
return d + 1;
}
};
迭代做法：
迭代做法相对麻烦一点，需要设置一个栈，栈的每个元素由树节点和深度构成。对树进行先序遍历，每次迭代出栈当前栈顶节点，同时用该节点的深度更新最大深度，然后依次入栈右孩子和左孩子。
time: 72.84%, memory: 5.14%
/**
* 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:
struct DPair{
TreeNode *node;
int d;
DPair(int dep, TreeNode *n): d(dep), node(n) {}
};
int maxDepth(TreeNode* root) {
if(!root) return 0;
stack<DPair> s;
TreeNode *c = root;
int max_dep = 0;
s.push(DPair(1, c));
DPair p = DPair(0, NULL);
while(!s.empty()){
p = s.top();
s.pop();
if(p.node -> right)
s.push(DPair(p.d + 1, p.node -> right));
if(p.node -> left)
s.push(DPair(p.d + 1, p.node -> left));
if(p.d > max_dep) max_dep = p.d;
}
return max_dep;
}
};
98 验证二叉搜索树
标签：二叉树遍历，中序遍历
不愧是中等题，提交了好多次。中等题目教我做人。
误区：开始以为简单递归一下就行，但是这样只能保证直接后继满足搜索关系，不能保证整棵树满足搜索关系。所以需要提供一个额外的遍历函数。
- 后序遍历
开始采用了后序遍历的做法，这种做法是通过返回更多数值来实现的。设计一种结构体Ret，每次迭代返回当前子树的最小值和最大值，用来跟父节点进行比较，但是这样写出来代码比较长，而且个人也觉得这种解法不漂亮。
24ms, 24.8M
/**
* 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:
struct Ret{
bool is_valid;
int min_ele, max_ele;
Ret(bool v, int min, int max): is_valid(v), min_ele(min), max_ele(max) {}
};
Ret ValidCheck(TreeNode *root){
if(!root) return Ret(true, INT_MIN, INT_MAX);
Ret l(true, root -> val, root -> val), r(true, root -> val, root -> val);
if(root -> left){
l = ValidCheck(root -> left);
}
if(root -> right){
r = ValidCheck(root -> right);
}
if(!l.is_valid || !r.is_valid)
return Ret(false, 0, 0);
if(root -> left && l.max_ele >= root -> val)
return Ret(false, 0, 0);
if(root -> right && r.min_ele <= root -> val)
return Ret(false, 0, 0);
return Ret(true, l.min_ele, r.max_ele);
}
bool isValidBST(TreeNode* root) {
return ValidCheck(root).is_valid;
}
};
- 先序遍历
后来改用了先序遍历的方法，通过提供更多的参数来实现。每次提供从根节点到当前节点的子树的上界和下界，用来跟当前节点比较。这种做法比较恶心的地方是，因为最开始需要提供平凡的一个最小值和最大值，当当前节点的值是INT_MAX或者INT_MIN时，就会判断错误。后来采用了整数指针，一开始为空，后面再赋值，就可以排除因为节点的极值导致判断错误的问题。
代码：
20ms, 24.2M
/*
* 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 ValidCheck(TreeNode *root, int *lower, int *upper){
if(lower && root -> val <= *lower) return false;
if(upper && root -> val >= *upper) return false;
bool l = true, r = true;
if(root -> left)
l = ValidCheck(root -> left, lower, &(root -> val));
if(root -> right)
r = ValidCheck(root -> right, &(root -> val), upper);
return l && r;
}
bool isValidBST(TreeNode* root) {
if(!root) return true;
return ValidCheck(root, NULL, NULL);
}
};
比较上面两种做法，第一种是自底向上的思想，用左子树和右子树分别提供当前节点的上下界；第二种是自顶向下的思想，用从根节点到当前节点的路径上的节点来提供上下界。
-
中序遍历
中序遍历真的是中非常非常巧妙的做法，仔细想一下，就会发现，中序遍历的顺序恰好是树的搜索顺序，也就是说，如果一棵树满足搜索顺序，那么，中序遍历的过程中，后面的元素一定比前面大。
换一种方法解释，将当前树分为左子树，父节点，右子树三部分，我们需要的就是，左子树的值都比父节点小，右子树的值都比父节点大，这恰好就是中序遍历的顺序。真的很巧妙，我壶了。
32ms, 23.9M
/**
* 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) return true;
int *cur_max = NULL;
stack<TreeNode*> s;
s.push(root);
TreeNode* t = root -> left;
while(!s.empty() || t){
while(t){
s.push(t);
t = t -> left;
}
t = s.top();
s.pop();
if(cur_max && ((t -> val) <= *cur_max))
return false;
cur_max = &(t -> val);
t = t -> right;
}
return true;
}
};
总结：先序遍历是一种自顶向下的遍历方法，父节点先于两个子树，后序遍历则是自底向上，先子树后父节点，而中序遍历则是二分的想法，通过父节点将两棵子树区分开。
这道题是一个很好的题目，不仅可以考虑多种遍历方法来解，同时更启发我们去思考，每种遍历方法的本质是什么，对于一个问题来说，更适合的遍历方法是什么。
