剑指Offer（数据结构与算法面试题精讲）C++版——day17

题目一：节点值之和最大的路径

    题目：在二叉树中将路径定义为顺着节点之间的连接从任意一个节点开始到达任意一个节点所经过的所有节点。路径中至少包含一个节点，不一定经过二叉树的根节点，也不一定经过叶节点。给定非空的一棵二叉树，请求出二叉树所有路径上节点值之和的最大值。例如，在如图8.6所示的二叉树中，从节点15开始经过节点20到达节点7的路径的节点值之和为42，是节点值之和最大的路径。
    根据示例可以得到，这里的最大和路径可以从左侧节点绕过父节点再走到右侧。回顾前面剑指Offer（数据结构与算法面试题精讲）C++版——day16中的题目三（向下的路径节点值之和），因为需要遍历从根节点遍历到所有的叶子节点，整体上需要满足一种自上而下的结构，而这里需要的考虑绕过根节点，于是可以想到将前序遍历改成后序遍历，保证这里的路径能够从左到右绕过父节点探索。
    但是，这样显然不够，因为如果简单使用后续遍历会发现，15，7这种路径不能够存在，因为没有直接节点相连，并且如果选择了15，20，7这样的路径，那么不能够再选择当前20节点的父节点，因为这种结构存在路径重复，与题意不符。于是想到我们对于一个新节点的遍历，应该考虑如下三种情况：
（1）沿着该节点向左孩子遍历；
（2）沿着该节点向右孩子遍历；
（3）舍弃前面的遍历结果，考虑左孩子->父节点->右节点遍历；
    最终得到如下代码：

int maxSum = INT_MIN;
int dfs(treeNode* tree) {
	if (tree == nullptr){
		return 0;
	}
	int leftMax = max(0, dfs(tree->left));//若左右分支返回的值为负数，则对路径和做负贡献，直接舍弃
	int rightMax = max(0, dfs(tree->right));
	int leftAndRight = leftMax + tree->val + rightMax; //可能为left->root->right,使用了后续不可再延伸 
	maxSum = max(maxSum, leftAndRight);
	return tree->val + max(leftMax, rightMax);//向node的父结点返回经过node的单边分支的最大路径和
}

int maxPathSum(treeNode* tree) { 
	dfs(tree);
	return maxSum;
}

    这道题的代码其实不是很好想，在leetcode上面这是一道hard题，我这里也是看了很多题解介绍才搞明白的。为了方便理解这里将maxSum设置成全局变量，在实际算法题中其实是可行的（如果不太习惯这种写法那其实也可以将maxSum设置成一个引用类型对象，本质上差不多）。在理解时可以先不考虑“左根右”这种遍历方式，整个代码就更方便理解了，一开始分别计算左右子树的和，如果左子树大接下来进入左子树，右子树大进入右子树，因为如果子树更小，那不如直接取另外一边，之所以深度递归下去是为了检测是否还有负数值产生干扰以提前裁剪。这样遍历的整体形式就是自上而下了，为了考虑到“左根右”遍历，再补上这样计算与总和的大小比较取max，这样整个代码就清晰很多了。

题目二：展平二叉搜索树

    题目：给定一棵二叉搜索树，请调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树。例如，把图8.8（a）中的二叉搜索树按照这个规则展平之后的结果如图8.8（b）所示。

    由题意可知这是一种中序遍历方式，只是需要维护节点不能够具有左子树。这里有一种暴力思路，先按照中序遍历的方式遍历这棵二叉搜索树，遍历完将节点值压入到队列中，然后删除节点，之后利用队列中的值重新构建一棵二叉树。但这里还有一种更好的方式，不需要删除树和重建，而是采用栈存储节点，然后再调整指针指向，因为涉及到修改指针指向，所以这里应该使用中序遍历的非递归写法（非递归写法思路见第三题），然后利用临时指针记录前一个指针，实现逆序构建指针指向，最终得到代码如下：

treeNode * flattenTree(treeNode* tree) {
	treeNode* current=tree,*pre=nullptr,*root=nullptr;
	stack<treeNode* > st;
	while(current||!st.empty()) {
		while(current) {//找到最左边元素
			st.push(current);
			current=current->left;
		}
		current=st.top();
		st.pop();
		if(pre) {//检查节点是否第一个出现，记录根节点并修改指向 
			pre->right=current;
		} else {
			root=current;
		}
		pre=current; 
		current->left=nullptr;
		current=current->right;
	}
	return root;
}

题目三：二叉搜索树的下一个节点

    题目：给定一棵二叉搜索树和它的一个节点p，请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如，在图8.9的二叉搜索树中，节点8的下一个节点是节点9，节点11的下一个节点是null。

    结合前面第二题，这里就比较简单了，同样是利用中序遍历的非递归写法，由于第二题没有详细说明二叉树中序遍历的非递归写法思路，这里刚好补上。我们在中序遍历时，首先需要拿到最左下角元素，然后遍历“根节点”，再来遍历右子树，在右子树中还是需要先找到右子树的最左侧节点，这就是为什么中序遍历的非递归写法中会出现两个while循环。然后对于中间的“根节点”使用栈来维护，因为最左侧的节点先一步出栈，之后是这些中间“根节点”，所以在第二个while中会提前将current节点入栈，如果拿到最后一个比如这里的节点5，其后没有节点了，那么在栈中取节点，这时就回到了中间“根节点”6，之后换入到右子树，按照前面的步骤接着进行。这里你可能想到可能current->right为空，比如这里7节点扫描完成之后，接下来访问的节点就是空节点了，这里就巧妙利用了第一层while的判定条件，只要current为空但栈中有节点那么弹出栈中元素，保证了整个中序遍历的完整性。

treeNode * getNextNode(treeNode* tree,int val) {
	treeNode* current=tree,*pre=nullptr;
	stack<treeNode* > st;
	while(current||!st.empty()) {
		while(current) {//找到最左边元素
			st.push(current);
			current=current->left;
		}
		current=st.top();
		st.pop();
		if(pre&&pre->val==val) {//取出二叉搜索树的下一个节点
			return current;
		}
		pre=current;
		current=current->right;
	}
	return nullptr;
}

    当然这里还有一种思路更加高效，利用二叉搜索树的特点，由于这里每个节点的值唯一，可以将题意理解成找到二叉搜索树中目标节点的最近的下一个节点，那么可以从根节点开始遍历，如果当前值大于指定值，那么存储这个可能的节点，然后再去左子树中找可能更接近的点；如果左子树中没有更大节点，那么和上面的思路一样，开始遍历右侧子树。这种思路下不需要使用到栈，节省了空间，同时只需要从上到下遍历，时间复杂度也从原来的O(n)变成了O(h)。得到的代码如下：

treeNode * getNextNodeWithoutStack(treeNode* tree,int val) {
	treeNode * result=nullptr,*current=tree;
	while(current) {
		if(current->val>val){//利用二叉搜索树的顺序性，目标是找到比当前节点大的最近节点 
			result=current;
			current=current->left;
		}else{
			current=current->right;	
		}
	}
	return result;
}

附录：源码gitee仓库

    考虑到有些算法需要模拟数据，如果全部放进来代码显得过长，不利于聚焦在算法的核心思路上。于是把所有的代码整理到了开源仓库上，如果想要看详细模拟数据，可在开源仓库自取：【凌空暗羽/剑指Offer-C++版手写代码】。

    我是【Jerry说前后端】，本系列精心挑选的算法题目均基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
    无论是即将踏入职场的应届毕业生，还是想要进一步提升自身技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！