九章算法
前⾔
第⼀天的算法都还没有缓过来，直接就进⼊了第⼆天的算法学习。前⼀天⼀直在整理Binary Search的笔记，也没有提前预习⼀下，好在Binary Tree算是⾃⼰最熟的地⽅了吧（LeetCode上⾯Binary Tree的题刷了4遍，⽬前95%以上能够Bug Free）所以还能跟得上，今天听了⼀下，觉得学习到最多的，就是把Traverse和Divide Conquer分开来讨论，觉得开启了⼀⽚新的天地！今天写这个博客我就尽量把两种⽅式都写⼀写吧。
Outline:
⼆叉树的遍历
前序遍历traverse⽅法
前序遍历⾮递归⽅法
前序遍历分治法
遍历⽅法与分治法
Maximum Depth of Binary Tree
Balanced Binary Tree
⼆叉树的最⼤路径和 (root->leaf)
Binary Tree Maximum Path Sum II (root->any)
Binary Tree Maximum Path Sum (any->any)
⼆叉查树
Validate Binary Search Tree
Binary Search Tree Iterator
⼆叉树的宽度优先搜索
Binary Tree Level-Order Traversal
课堂笔记
1.⼆叉树的遍历
这个应该是⼆叉树⾥⾯最基本的题了，但是在⾯试过程中，不⼀定会考递归的⽅式，很有可能会让你写出⾮递归的⽅法，上课的时候⽼师也提到过，应该直接把⾮递归的⽅法背下来。这⾥我就不多说了，直接把中序遍历的两种⽅法贴出来吧，最后再加⼊⼀个分治法（这也是第⼀次写，感觉很棒呢，都不需要太多的思考）。
1.1 前序遍历traverse⽅法（Bug Free）：
vector<int> res;
void helper(TreeNode* root) {
if (!root) return;
res.push_back(root->val);
if (root->left) {
helper(root->left);
}
if (root->right) {
helper(root->right);
}
}
vector<int> preorderTraversal(TreeNode *root) {
if (!root) {
return res;
}
helper(root);
return res;
}
1.2 前序遍历⾮递归⽅法（Bug Free）：
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) {
return res;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* tmp = s.top();
s.pop();
res.push_back(tmp->val);
// 这⾥注意：栈是先进后出，所以先push右⼦树
if (tmp->right) {
s.push(tmp->right);
}
二叉树中序遍历非递归算法if (tmp->left) {
s.push(tmp->left);
}
}
return res;
}
1.3 前序遍历分治法（Java实现）：
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) {
return res;
}
//Divide
vector<int> left = preorderTraversal(root->left);
vector<int> right = preorderTraversal(root->right);
//Conquer
res.push_back(root->val);
res.d(), left.begin(), d());
res.d(), right.begin(), d());
return res;
}
这三种⽅法也是⽐较直观的，前两个⽐较基础，我就不详细叙述了，但是分治法是值得重点说⼀说的。前⾯的遍历的⽅法是需要对每⼀个点进⾏判断和处理的，根据DFS进⼊到每⼀个节点，然后操作；但是使⽤分治法的话，就不需要考虑那么多，分治法的核⼼思想就是把⼀个整体的问题分为多个⼦问题来考虑，也就是说：每⼀个⼦问题的操作⽅法都是⼀样的，⼦问题的解是可以合并为原问题的解的（这⾥就是和动态规划、贪⼼法不⼀样的地⽅）。所以使⽤分治法的话，就不需要对每个节点都进⾏判断，不管左右⼦树的情况（是否存在），直接进⾏求解，最后把它们合并起来。上课的时候⽼师也说过分治法就像⼀个⼥王⼤⼈，处于root的位置，然后派了两位青蛙⼤⾂去处理⼀些事物，⼥王⼤⼈只需要管好⾃⼰的val是多少，然后把两个⼤⾂的反馈直接加起来就可以了。个⼈认为分治法算是⽐较接近普通⼈思维的⼀种⽅法了。
2. 遍历⽅法与分治法
遍历⽅法其实在我经过之前各种刷题套模板后算是能够熟悉掌握了，所谓“虽不知其内涵，但知其模板”的境界，今天这个总结，确实帮助不少。直接承接了上⾯所说的两种思考。接下来我就直接⽤题解来分析⼀下：
2.1 Maximum Depth of Binary Tree
给定⼀个⼆叉树，出其最⼤深度。
⼆叉树的深度为根节点到最远叶⼦节点的距离。
样例
给出⼀棵如下的⼆叉树:
1
/ \
2  3
/ \
4  5
这个⼆叉树的最⼤深度为3.
这个题⽬要是在⾯试的时候⾯到，那绝对可以⼀分钟内写出来，因为如果考虑分治法的话，就是⼀个简单的DFS，代码如下（Bug Free）：    public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left) + 1;
int right = maxDepth(root.right) + 1;
return left > right ? left : right;
}
就是递归查看左右两边最⼤的深度，然后返回就可以。这个思路也⽐较简单，我就不多说了。
接下来再来⼀个题⽬：
2.2 Balanced Binary Tree
给定⼀个⼆叉树，确定它是⾼度平衡的。对于这个问题,⼀棵⾼度平衡的⼆叉树的定义是：⼀棵⼆叉树中每个节点的两个⼦树的深度相差不会超过1。
样例
给出⼆叉树 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A)  3            B)    3
/ \                  \
9  20                20
/  \                / \
15  7              15  7
⼆叉树A是⾼度平衡的⼆叉树，但是B不是
这个题⽬思路也⽐较简单，判断⼀下左右⼦树的⾼度差是否⼩于1，也是⼀个简单的分治法问题。因为课上⽤了⼀种Java的版本来写，加⼊了⼀个ResultType类，这⾥我也尝试着写了⼀下代码（Bug Free）：
class ResultType {
public boolean isBalanced;
public int MaxDepth;
public ResultType(boolean isBalanced, int MaxDepth) {
this.isBalanced = isBalanced;
this.MaxDepth = MaxDepth;
}
}
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
public boolean isBalanced(TreeNode root) {
return helper(root).isBalanced;
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(true, 0);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
if (!left.isBalanced || !right.isBalanced) {
return new ResultType(false, -1);
}
if (Math.abs(left.MaxDepth - right.MaxDepth) > 1) {
return new ResultType(false, -1);
}
return new ResultType(true, Math.max(left.MaxDepth, right.MaxDepth) + 1);
}
}
这⾥的ResultType保存了⼀个布尔值判断⼦树是否是平衡⼆叉树，⽤⼀个最⼤深度表⽰该⼦树的最⼤深度。然后在Divide阶段，分别递归调⽤了左右⼦树，之后判断左右⼦数的最⼤深度差，并且判断它们是否满⾜平衡⼆叉树，最后返回该⼦树的最⼤深度。这个思考也是⽐较⾃然合理的。运⽤了这种调⽤类的⽅式来进⾏解答，颇有⼀番⾯向对象的感觉，但是本⼈是不太喜欢这种⽅式的，因为不容易思考，还需要考虑很多⾃⼰不熟悉的地⽅，容易出错。
接下来就是本篇⽂章的重要部分了。我要详细描述⼀下⼆叉树的最⼤路径这个问题，记得有⼀次⾯试还⾯到过这个题，我也要把不同的情况写出来。
先来最简单的部分吧，给⼀棵⼆叉树，出从根节点出发到叶节点的路径中，和最⼤的⼀条。这个就⽐较简单了，直接遍历整个树，然后到最⼤的路径即可，这⾥我就不多说了，⽐较简单。直接上题⽬吧：
2.3 （1）⼆叉树的最⼤路径和（root->leaf）
给⼀棵⼆叉树，出从根节点出发到叶节点的路径中，和最⼤的⼀条。
样例
给出如下的⼆叉树：
1
/ \
2  3
返回4。(最⼤的路径为1→3)
就不需要多解释了，我就直接把代码贴出来（Bug Free）：
public int maxPathSum2(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxPathSum2(root.left);
int right = maxPathSum2(root.right);
return root.val + Math.max(left, right);
}
（2）⼆叉树的最⼤路径和（root->any）
2.4 Binary Tree Maximum Path Sum II
给⼀棵⼆叉树，出从根节点出发的路径中，和最⼤的⼀条。
这条路径可以在任何⼆叉树中的节点结束，但是必须包含⾄少⼀个点（也就是根了）。
样例
给出如下的⼆叉树：
1
/ \
2  3
返回4。(最⼤的路径为1→3)
这个就跟原始版的题⽬不⼀样了，这⾥是从根到任意的节点，当然就不能采⽤原始问题的⽅法了，不然就是指数级别的复杂度了，这⾥就采⽤分治法了：
我们把分治的基本思想考虑进去：
1.递归的出⼝：当节点为null
2.Divide：分别对左右进⾏递归
3.Conquer：把得到的结果进⾏操作。
Java代码如下（Bug Free）：
public int maxPathSum2(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxPathSum2(root.left);
int right = maxPathSum2(root.right);
return root.val + Math.max(0, Math.max(left, right));
}
这⾥有⼀个关键点，对于某⼀个节点来说，得到了左右⼦树的和，这⾥我就要判断是否加上⼦树（这个部分就是和原始问题不⼀样的地⽅，保证了是任意的节点），加上⼦树的话是加左⼦树还是右⼦树，然后就能得到最⼤值了。这个题最⼤的关键还是在于不考虑左右⼦树如何，就把他们派出去，得到结果以后再进⾏判断。
（3）⼆叉树中的最⼤路径和（any->any）
2.5 Binary Tree Maximum Path Sum
给出⼀棵⼆叉树，寻⼀条路径使其路径和最⼤，路径可以在任⼀节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）
样例
给出⼀棵⼆叉树：
  1
/ \
2  3
返回6
这个题是上⼀个题⽬的升级版，这⾥求的就是任意两个点的最⼤路径和了。这样的题其实就是从上⾯的题做了⼀个引申，不过之前的题必须
考虑到root，所以就直接判断左右⼦树，⽽这⾥的话，就不需要考虑root了，所以问题就变成了⼀个“把每⼀个节点都当作root来考虑的问题”，这⾥是我⾃⼰的理解，可能我没有表达清楚，也就是说，在每⼀步递归中，都需要把当前的root考虑为上⼀题中的root，然后来判断哪个root得到的值是最⼤的。所以这⾥就需要增加⼀个全局变量来存储了。代码如下：
int Max = INT_MIN;
int helper(TreeNode *root) {
if (!root) {
return 0;
}
int tmp = root->val;
//Divide
int left = helper(root->left);
int right = helper(root->right);
//Conquer
if (left > 0) {
tmp += left;
}
if (right > 0) {
tmp += right;
}
Max = max(Max, tmp);
return max(0,max(left,right)) + root->val;
}
int maxPathSum(TreeNode *root) {
int t = helper(root);
return Max;
}
这道题其实我在很久前的⼀次⾯试中就被问到过，当时⾯试官的描述就是⽐较奇怪，并没有说any to any的问题，⽽是说任意⼀段路径，但是不能有分叉。其实回过头来思考，这个题也确实需要考虑这个问题：不能有分叉！如果允许分叉的话，那么这个问题就没有那么简单了。当时我就半天没有写出来，⽽这次在lintcode上能做到Bug Free，果然还是⼀个完全不擅于上战场的⼈啊( ▼-▼ )。这个题关键就在于你要去判断左右⼦树的值是否会让这⼀个⼩团的值变⼩，如果会，那就不加上左右⼦树。最后的return也是⼀个关键的地⽅：因为不能有分叉，所以只返回⼀条路径。
这两个题⽬就是充分运⽤了分治的⽅法，还需要⼤家很深刻的去理解⼀下其中的内涵，还是有⼀些需要思考的地⽅。
3. ⼆叉查树
个⼈认为在树的题⽬中，最令⼈开⼼的就是⼆叉查树了，因为这种结构本⾝就带有⼀种光环：左⼦树⼩于root，右⼦树⼤于root，这⽅⾯的题只需要紧紧围绕这个概念来做就可以。
直接上⼀个课上说过的题吧：
3.1 Validate Binary Search Tree
给定⼀个⼆叉树，判断它是否是合法的⼆叉查树(BST)
⼀棵BST定义为：
节点的左⼦树中的值要严格⼩于该节点的值。
节点的右⼦树中的值要严格⼤于该节点的值。
左右⼦树也必须是⼆叉查树。
⼀个节点的树也是⼆叉查树。
样例
⼀个例⼦：
2
/ \
1  4
/ \
3  5
上述这棵⼆叉树序列化为{2,1,4,#,#,3,5}.
看了这道题，我的第⼀个想法就是，判断左边最⼤的是否⼩于root，然后判断右边最⼩的是否⼤于root，然后递归去判断。这个算法复杂度也⽐较⾼，最后还是过了，可以贴上来给⼤家看看：
bool isValidBST(TreeNode *root) {
if (!root) {
return true;
}
if (root->left) {

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。