LeetCode 971. 翻转二叉树以匹配先序遍历（DFS）
LeetCode 971. 翻转二叉树以匹配先序遍历（DFS）
Michael阿明
发布于 2020-07-13 15:15:44
发布于 2020-07-13 15:15:44
1. 题目
给定一个有 N 个节点的二叉树，每个节点都有一个不同于其他节点且处于 {1, …, N} 中的值。
通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。
考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。
（回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。）
我们的目标是翻转最少的树中节点，以便树的行程与给定的行程 voyage 相匹配。
如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。
如果不能，则返回列表 [-1]。
示例 1：
在这里插入图片描述
输入：root = [1,2], voyage = [2,1]
输出：[-1]示例 2：
在这里插入图片描述
输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]示例 3：
在这里插入图片描述
输入：root = [1,2,3], voyage = [1,2,3]
输出：[]
提示：
1 <= N <= 100来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/flip-binary-tree-to-match-preorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 边先序遍历，边调换左右子树节点
class Solution { //C++
int i = 0;
bool can = true;
vector<int> ans;
public:
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
dfs(root, voyage);
if(!can) return {-1};
return ans;
}
void dfs(TreeNode* root, vector<int>& voyage)
{
if(!can || !root)
return;
if(root->val == voyage[i])
{ //根值等于数字
i++;//指针后移一位
if(root->left && root->left->val == voyage[i])
{ //左边有节点，值等于下一个，正常遍历
dfs(root->left, voyage);
dfs(root->right, voyage);
}
else if(root->right && root->right->val == voyage[i])
{ //右边右节点，值等于下一个
if(root->left)//如果还有左节点，那说明要调换左右顺序
ans.push_back(root->val);
dfs(root->right, voyage);
dfs(root->left, voyage);
}
else if(root->left || root->right)
can = false;//如果上面分支都没有进入，且还有子节点，说明不能匹配
}
else//根值不等，返回错误
can = false;
}
};8 ms 13.3 MB
python3 解答
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution: # py3
def __init__(self):
self.i = 0
self.can = True
self.ans = []
def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:
def dfs(root, voyage):
if not self.can or not root:
return
if root.val == voyage[self.i]:
self.i += 1
if root.left and root.left.val == voyage[self.i]:
dfs(root.left,voyage)
dfs(root.right, voyage)
elif root.right and root.right.val == voyage[self.i]:
if root.left:
self.ans.append(root.val)
dfs(root.right, voyage)
dfs(root.left, voyage)
elif root.left or root.right:
self.can = False
else:
self.can = False
dfs(root, voyage)
if not self.can:
return [-1]
return self.ans40 ms 13.7 MB
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-06-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录