淮北矿业 集团 工程建设有限责任公司网站,知名商城网站建设多少钱,徐州网站建设要多少钱,天津环保网站建设概念1. 题目
给定一个有 N 个节点的二叉树#xff0c;每个节点都有一个不同于其他节点且处于 {1, …, N} 中的值。
通过交换节点的左子节点和右子节点#xff0c;可以翻转该二叉树中的节点。
考虑从根节点开始的先序遍历报告的 N 值序列。将这一 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 { //Cint i 0;bool can true;vectorint ans;
public:vectorint flipMatchVoyage(TreeNode* root, vectorint voyage) {dfs(root, voyage);if(!can) return {-1};return ans;}void dfs(TreeNode* root, vectorint 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 Noneclass Solution: # py3def __init__(self):self.i 0self.can Trueself.ans []def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) - List[int]:def dfs(root, voyage):if not self.can or not root:returnif root.val voyage[self.i]:self.i 1if 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 Falseelse:self.can Falsedfs(root, voyage)if not self.can:return [-1]return self.ans40 ms 13.7 MB
