海珠建网站公司,全国精品课程建设网站,电商平面设计工作内容,做网站的公司算外包公司吗文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;翻转二叉树以匹配前序遍历
出处#xff1a;971. 翻转二叉树以匹配前序遍历
难度
5 级
题目描述
要求
给定一个二叉树的根结点 root \texttt{roo… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题翻转二叉树以匹配前序遍历
出处971. 翻转二叉树以匹配前序遍历
难度
5 级
题目描述
要求
给定一个二叉树的根结点 root \texttt{root} root二叉树中有 n \texttt{n} n 个结点每个结点都有一个 1 \texttt{1} 1 到 n \texttt{n} n 之间的值且不同结点的值各不相同。另外给定一个由 n \texttt{n} n 个值组成的行程序列 voyage \texttt{voyage} voyage表示预期的二叉树前序遍历结果。
通过交换结点的左右子树可以翻转该二叉树中的任意结点。例如翻转结点 1 \texttt{1} 1 的效果如下 请翻转最少的树中结点使得二叉树的前序遍历与预期的遍历行程 voyage \texttt{voyage} voyage 相匹配。
返回翻转的所有结点的值的列表。可以按任何顺序返回答案。如果不能则返回列表 [-1] \texttt{[-1]} [-1]。
示例
示例 1 输入 root [1,2], voyage [2,1] \texttt{root [1,2], voyage [2,1]} root [1,2], voyage [2,1] 输出 [-1] \texttt{[-1]} [-1] 解释翻转结点无法令前序遍历匹配预期行程。
示例 2 输入 root [1,2,3], voyage [1,3,2] \texttt{root [1,2,3], voyage [1,3,2]} root [1,2,3], voyage [1,3,2] 输出 [1] \texttt{[1]} [1] 解释翻转结点 1 \texttt{1} 1 交换结点 2 \texttt{2} 2 和 3 \texttt{3} 3使得前序遍历可以匹配预期行程。
示例 3 输入 root [1,2,3], voyage [1,2,3] \texttt{root [1,2,3], voyage [1,2,3]} root [1,2,3], voyage [1,2,3] 输出 [] \texttt{[]} [] 解释前序遍历已经匹配预期行程所以不需要翻转结点。
数据范围
树中结点数目为 n \texttt{n} n n voyage.length \texttt{n} \texttt{voyage.length} nvoyage.length 1 ≤ n ≤ 100 \texttt{1} \le \texttt{n} \le \texttt{100} 1≤n≤100 1 ≤ Node.val, voyage[i] ≤ n \texttt{1} \le \texttt{Node.val, voyage[i]} \le \texttt{n} 1≤Node.val, voyage[i]≤n树中的所有值各不相同 voyage \texttt{voyage} voyage 中的所有值各不相同
解法
思路和算法
二叉树的前序遍历的方法为依次遍历根结点、左子树和右子树对于左子树和右子树使用同样的方法遍历。对于每个结点如果不翻转该结点则遍历该结点之后依次遍历左子树和右子树如果翻转该结点则遍历该结点之后依次遍历右子树和左子树。由于题目要求翻转的结点数最少因此只有当必须翻转结点的时候才翻转结点。当遍历到一个结点时其子结点值和预期行程中的下一个值可能有以下情况。 当前结点的左子结点为空或者左子结点值和预期行程中的下一个值相同此时不需要翻转当前结点。 当前结点的左子结点不为空且左子结点值和预期行程中的下一个值不同如果不翻转当前结点则下一个访问的结点是左子结点无法匹配预期行程此时需要翻转当前结点。翻转当前结点之后不能保证匹配预期行程而是需要访问原右子结点判断当前结点的原右子结点值是否和预期行程中的下一个值相同可能有以下两种情况。 如果原右子结点值和预期行程中的下一个值相同则翻转当前结点之后原右子结点匹配预期行程继续遍历判断其余的结点是否匹配预期行程。 如果原右子结点值和预期行程中的下一个值不同则翻转当前结点之后仍无法匹配预期行程。由于当前结点无论是否翻转都无法匹配预期行程因此无法通过翻转二叉树中的结点匹配预期行程。
根据上述分析可以在二叉树前序遍历的基础上做修改得到翻转的结点值列表。从根结点开始前序遍历二叉树遍历过程中维护翻转的结点值列表并维护状态值记录是否存在翻转方案不存在翻转方案表示无法通过翻转二叉树中的结点匹配预期行程初始时翻转的结点值列表为空状态值为存在翻转方案具体做法如下。 如果当前结点为空或者状态值为不存在翻转方案则直接返回。 如果当前结点值和预期行程中的当前值不同则将翻转的结点值列表清空然后将 − 1 -1 −1 加入翻转的结点值列表并将状态值设为不存在翻转方案然后返回。 根据当前结点的左右子结点判断当前结点是否需要翻转并决定遍历左右子树的顺序。 如果当前结点的左子结点为空或者左子结点值和预期行程中的下一个值相同则不需要翻转当前结点依次对左子树和右子树前序遍历。 否则需要翻转当前结点将当前结点值加入翻转的结点值列表依次对右子树和左子树前序遍历。
遍历结束之后即可得到翻转的结点值列表。如果存在翻转方案则列表中的元素为所有需要翻转的结点值特别地当列表为空时表示原二叉树已经匹配预期行程因此不需要翻转任何结点如果不存在翻转方案则列表中只有一个元素 − 1 -1 −1。
代码
class Solution {ListInteger flips;int[] voyage;int n;int index;boolean possible;public ListInteger flipMatchVoyage(TreeNode root, int[] voyage) {this.flips new ArrayListInteger();this.voyage voyage;this.n voyage.length;this.index 0;this.possible true;preorder(root);return flips;}public void preorder(TreeNode node) {if (node null || !possible) {return;}if (node.val ! voyage[index]) {flips.clear();flips.add(-1);possible false;return;}index;TreeNode left node.left, right node.right;if (left null || left.val voyage[index]) {preorder(left);preorder(right);} else {flips.add(node.val);preorder(right);preorder(left);}}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。注意返回值不计入空间复杂度。
