2196. Create Binary Tree From Descriptions Medium

1/**
2 * [2196] Create Binary Tree From Descriptions
3 *
4 * You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,
5 * 
6 * 	If isLefti == 1, then childi is the left child of parenti.
7 * 	If isLefti == 0, then childi is the right child of parenti.
8 * 
9 * Construct the binary tree described by descriptions and return its root.
10 * The test cases will be generated such that the binary tree is valid.
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2022/02/09/example1drawio.png" style="width: 300px; height: 236px;" />
14 * Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
15 * Output: [50,20,80,15,17,19]
16 * Explanation: The root node is the node with value 50 since it has no parent.
17 * The resulting binary tree is shown in the diagram.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2022/02/09/example2drawio.png" style="width: 131px; height: 300px;" />
21 * Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
22 * Output: [1,2,null,null,3,4]
23 * Explanation: The root node is the node with value 1 since it has no parent.
24 * The resulting binary tree is shown in the diagram.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	1 <= descriptions.length <= 10^4
30 * 	descriptions[i].length == 3
31 * 	1 <= parenti, childi <= 10^5
32 * 	0 <= isLefti <= 1
33 * 	The binary tree described by descriptions is valid.
34 * 
35 */
36pub struct Solution {}
37use crate::util::tree::{TreeNode, to_tree};
38
39// problem: https://leetcode.com/problems/create-binary-tree-from-descriptions/
40// discuss: https://leetcode.com/problems/create-binary-tree-from-descriptions/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44// Definition for a binary tree node.
45// #[derive(Debug, PartialEq, Eq)]
46// pub struct TreeNode {
47//   pub val: i32,
48//   pub left: Option<Rc<RefCell<TreeNode>>>,
49//   pub right: Option<Rc<RefCell<TreeNode>>>,
50// }
51// 
52// impl TreeNode {
53//   #[inline]
54//   pub fn new(val: i32) -> Self {
55//     TreeNode {
56//       val,
57//       left: None,
58//       right: None
59//     }
60//   }
61// }
62use std::rc::Rc;
63use std::cell::RefCell;
64impl Solution {
65    pub fn create_binary_tree(descriptions: Vec<Vec<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
66        Some(Rc::new(RefCell::new(TreeNode::new(0))))
67    }
68}
69
70// submission codes end
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test_2196() {
78    }
79}
80