1448. Count Good Nodes in Binary Tree Medium

1/**
2 * [1448] Count Good Nodes in Binary Tree
3 *
4 * Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
5 * 
6 * Return the number of good nodes in the binary tree.
7 * 
8 *  
9 * Example 1:
10 * 
11 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/02/test_sample_1.png" style="width: 263px; height: 156px;" />
12 * 
13 * 
14 * Input: root = [3,1,4,3,null,1,5]
15 * Output: 4
16 * Explanation: Nodes in blue are good.
17 * Root Node (3) is always a good node.
18 * Node 4 -> (3,4) is the maximum value in the path starting from the root.
19 * Node 5 -> (3,4,5) is the maximum value in the path
20 * Node 3 -> (3,1,3) is the maximum value in the path.
21 * 
22 * Example 2:
23 * 
24 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/02/test_sample_2.png" style="width: 157px; height: 161px;" />
25 * 
26 * 
27 * Input: root = [3,3,null,4,2]
28 * Output: 3
29 * Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
30 * 
31 * Example 3:
32 * 
33 * 
34 * Input: root = [1]
35 * Output: 1
36 * Explanation: Root is considered as good.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 
42 * 	The number of nodes in the binary tree is in the range [1, 10^5].
43 * 	Each node's value is between [-10^4, 10^4].
44 * 
45 */
46pub struct Solution {}
47use crate::util::tree::{TreeNode, to_tree};
48
49// problem: https://leetcode.com/problems/count-good-nodes-in-binary-tree/
50// discuss: https://leetcode.com/problems/count-good-nodes-in-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54// Definition for a binary tree node.
55// #[derive(Debug, PartialEq, Eq)]
56// pub struct TreeNode {
57//   pub val: i32,
58//   pub left: Option<Rc<RefCell<TreeNode>>>,
59//   pub right: Option<Rc<RefCell<TreeNode>>>,
60// }
61// 
62// impl TreeNode {
63//   #[inline]
64//   pub fn new(val: i32) -> Self {
65//     TreeNode {
66//       val,
67//       left: None,
68//       right: None
69//     }
70//   }
71// }
72use std::rc::Rc;
73use std::cell::RefCell;
74impl Solution {
75    pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
76        0
77    }
78}
79
80// submission codes end
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    #[test]
87    fn test_1448() {
88    }
89}
90