给定一个有 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
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.ans
40 ms 13.7 MB