Rust | DFS | With Comments
I attempted to solve this for the 2022-10-30 Weekly Contest 317. Collect a map of the tree node levels, keyed by node value. At the same time, we make another m
I attempted to solve this for the 2022-10-30 Weekly Contest 317. Collect a map of the tree node levels, keyed by node value. At the same time, we make another map of the maximum levels of the tree nodes under each node, keyed by level (`levels`). For each query, we can then look up the level of that node. We use the level to look up the other nodes on that level in `levels`. If the queried node is the only node on that level, the resulting tree is `level - 1` high, since we will remove all levels below. If there are other nodes, the result is the maximum of the maximum levels of those nodes.\n\nComments:\n* I first went down the wrong path and had to restart. I was five minutes late when I had a working solution. Too bad, but it was a nice exercise.\n\n```\nuse std::rc::Rc;\nuse std::cell::RefCell;\nuse std::collections::HashMap;\nimpl Solution {\n    fn map(node: Option<Rc<RefCell<TreeNode>>>, levels: &mut Vec<Vec<(i32, usize)>>, map: &mut HashMap<i32, usize>, level: usize) -> usize {\n        if let Some(node_rc) = node {\n            let node_ref = node_rc.borrow();\n            if levels.len() == level {\n                levels.push(vec![]);\n            }\n            let max_level = Self::map(node_ref.left.clone(), levels, map, level + 1)\n                .max(Self::map(node_ref.right.clone(), levels, map, level + 1));\n            levels[level].push((node_ref.val, max_level));\n            map.insert(node_ref.val, level);\n            max_level\n        } else {\n            level - 1\n        }\n    }\n\n    pub fn tree_queries(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<i32> {\n        let mut levels = vec![];\n        let mut map = HashMap::new();\n        Self::map(root, &mut levels, &mut map, 0);\n        queries.into_iter().map(|q| {\n            let &level = map.get(&q).unwrap();\n            if levels[level].len() == 1 {\n                (level - 1) as i32\n            } else {\n                levels[level].iter().filter_map(|(val, l)| (*val != q).then(|| {\n                    *l\n                })).max().unwrap() as i32\n            }\n        }).collect()\n    }\n}\n```
['Rust']