当前位置:网站首页>LeetCode每日一题(971. Flip Binary Tree To Match Preorder Traversal)
LeetCode每日一题(971. Flip Binary Tree To Match Preorder Traversal)
2022-07-06 06:26:00 【wangjun861205】
You are given the root of a binary tree with n nodes, where each node is uniquely assigned a value from 1 to n. You are also given a sequence of n values voyage, which is the desired pre-order traversal of the binary tree.
Any node in the binary tree can be flipped by swapping its left and right subtrees. For example, flipping node 1 will have the following effect:
Flip the smallest number of nodes so that the pre-order traversal of the tree matches voyage.
Return a list of the values of all flipped nodes. You may return the answer in any order. If it is impossible to flip the nodes in the tree to make the pre-order traversal match voyage, return the list [-1].
Example 1:
Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.
Example 2:
Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]
Explanation: Flipping node 1 swaps nodes 2 and 3, so the pre-order traversal matches voyage.
Example 3:
Input: root = [1,2,3], voyage = [1,2,3]
Output: []
Explanation: The tree’s pre-order traversal already matches voyage, so no nodes need to be flipped.
Constraints:
- The number of nodes in the tree is n.
- n == voyage.length
- 1 <= n <= 100
- 1 <= Node.val, voyage[i] <= n
- All the values in the tree are unique.
- All the values in voyage are unique.
用 preorder 来遍历树, 同时跟 vayage 进行对比, 如果左边节点的值与 voyage 的下一个值相等则用左边节点进行下一步的遍历, 如果右边节点的值与 voyage 的下一个值相等, 那就用右边的节点进行下一步的遍历。但是如果需要用右边节点进行遍历则证明左右两边节点需要互换,所以当前节点的值需要加到答案数组里。
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn rc(root: Option<Rc<RefCell<TreeNode>>>, voyage: &mut Vec<i32>) -> Vec<i32> {
if let Some(node) = root {
let v = voyage.remove(0);
if node.borrow().val != v {
return vec![-1];
}
let left = node.borrow_mut().left.take();
let right = node.borrow_mut().right.take();
let left_val = if let Some(l) = &left {
l.borrow().val
} else {
-1
};
let right_val = if let Some(r) = &right {
r.borrow().val
} else {
-1
};
if left_val == -1 && right_val == -1 {
return vec![];
}
if left_val == voyage[0] {
let mut l = Solution::rc(left, voyage);
if l == vec![-1] {
return vec![-1];
}
let mut r = Solution::rc(right, voyage);
if r == vec![-1] {
return vec![-1];
}
l.append(&mut r);
return l;
}
let mut l = Solution::rc(right, voyage);
if l == vec![-1] {
return vec![-1];
}
let mut r = Solution::rc(left, voyage);
if r == vec![-1] {
return vec![-1];
}
l.append(&mut r);
if left_val != -1 {
l.push(node.borrow().val);
}
return l;
}
vec![]
}
pub fn flip_match_voyage(
root: Option<Rc<RefCell<TreeNode>>>,
mut voyage: Vec<i32>,
) -> Vec<i32> {
Solution::rc(root, &mut voyage)
}
}
边栏推荐
- Is the test cycle compressed? Teach you 9 ways to deal with it
- org.activiti.bpmn.exceptions.XMLException: cvc-complex-type.2.4.a: 发现了以元素 ‘outgoing‘ 开头的无效内容
- MySQL5.72.msi安装失败
- Transfert des paramètres de la barre d'adresse de la page de liste basée sur jeecg - boot
- 翻译生物医学说明书,英译中怎样效果佳
- Biomedical localization translation services
- 今日夏至 Today‘s summer solstice
- Resttemplate and feign realize token transmission
- 利用快捷方式-LNK-上线CS
- 记一个基于JEECG-BOOT的比较复杂的增删改功能的实现
猜你喜欢
生物医学本地化翻译服务
基于JEECG-BOOT制作“左树右表”交互页面
如何做好互联网金融的英语翻译
利用快捷方式-LNK-上线CS
CS passed (cdn+ certificate) PowerShell online detailed version
英语论文翻译成中文字数变化
Career advancement Guide: recommended books for people in big factories
Apple has open source, but what about it?
How to translate professional papers and write English abstracts better
How do programmers remember code and programming language?
随机推荐
【MQTT从入门到提高系列 | 01】从0到1快速搭建MQTT测试环境
How to do a good job in financial literature translation?
生物医学英文合同翻译,关于词汇翻译的特点
论文翻译英译中,怎样做翻译效果好?
keil MDK中删除添加到watch1中的变量
Luogu p2089 roast chicken
On weak network test of special test
这些年用Keil遇到的坑
Advanced MySQL: Basics (1-4 Lectures)
Cannot create poolableconnectionfactory (could not create connection to database server. error
在JEECG-boot代码生成的基础上修改list页面(结合自定义的组件)
私人云盘部署
MFC 动态创建的对话框及改变控件的大小和位置
Changes in the number of words in English papers translated into Chinese
Black cat takes you to learn EMMC Protocol Part 10: EMMC read and write operation details (read & write)
Construction and integration of Zipkin and sleuth for call chain monitoring
Redis core technology and basic architecture of actual combat: what does a key value database contain?
Left matching principle of joint index
模拟卷Leetcode【普通】1447. 最简分数
关于新冠疫情,常用的英文单词、语句有哪些?