当前位置:网站首页>Leetcode daily question (971. flip binary tree to match preorder traversal)
Leetcode daily question (971. flip binary tree to match preorder traversal)
2022-07-06 06:35: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.
use preorder To traverse the tree , At the same time vayage Contrast , If the value of the left node is the same as voyage If the next value of is equal, the left node is used for the next traversal , If the value of the right node is the same as voyage The next value of is equal , Then use the node on the right to go through the next step . But if you need to traverse with the right node, it proves that the left and right nodes need to be interchanged , So the value of the current node needs to be added to the answer array .
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)
}
}
边栏推荐
- Today's summer solstice
- E-book CHM online CS
- Distributed system basic (V) protocol (I)
- org. activiti. bpmn. exceptions. XMLException: cvc-complex-type. 2.4. a: Invalid content beginning with element 'outgoing' was found
- Simulation volume leetcode [general] 1091 The shortest path in binary matrix
- Set the print page style by modifying style
- How to do a good job in financial literature translation?
- MySQL5.72.msi安装失败
- 模拟卷Leetcode【普通】1219. 黄金矿工
- keil MDK中删除添加到watch1中的变量
猜你喜欢
如何做好金融文献翻译?
生物医学英文合同翻译,关于词汇翻译的特点
Drug disease association prediction based on multi-scale heterogeneous network topology information and multiple attributes
Transfert des paramètres de la barre d'adresse de la page de liste basée sur jeecg - boot
MySQL5.72.msi安装失败
What are the commonly used English words and sentences about COVID-19?
[ 英语 ] 语法重塑 之 动词分类 —— 英语兔学习笔记(2)
Esp32 esp-idf watchdog twdt
Phishing & filename inversion & Office remote template
How do programmers remember code and programming language?
随机推荐
Tms320c665x + Xilinx artix7 DSP + FPGA high speed core board
How do programmers remember code and programming language?
私人云盘部署
Simulation volume leetcode [general] 1296 Divide an array into a set of consecutive numbers
Simulation volume leetcode [general] 1405 Longest happy string
Simulation volume leetcode [general] 1219 Golden Miner
Simulation volume leetcode [general] 1447 Simplest fraction
mysql按照首字母排序
Simulation volume leetcode [general] 1314 Matrix area and
模拟卷Leetcode【普通】1062. 最长重复子串
MySQL5.72.msi安装失败
翻译生物医学说明书,英译中怎样效果佳
Black cat takes you to learn UFS protocol Chapter 4: detailed explanation of UFS protocol stack
Error getting a new connection Cause: org. apache. commons. dbcp. SQLNestedException
Use shortcut LNK online CS
字幕翻译中翻英一分钟多少钱?
How effective is the Chinese-English translation of international economic and trade contracts
Full link voltage measurement: building three models
ECS accessKey key disclosure and utilization
Lecture 8: 1602 LCD (Guo Tianxiang)