1448. Count Good Nodes in Binary Tree

source: https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Question

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.

Return the number of good nodes in the binary tree.

初想法

这道题还是思路比较明确的，和父节点关系明显，用dfs去做最方便。

值得一提的是，这道题一开始我希望在dfs函数里直接传递i32的结果，但是发现很难计算，不如直接传一个可以share的引用对象数组，最后算他的长度。

pub fn good_nodes(root: Option<Rc<RefCell<TreeNode<i32>>>>) -> i32 {
    if root.is_none() {
        return 0;
    }
    fn dfs(node: Option<Rc<RefCell<TreeNode>>>, ret: &mut Vec<i32>, max: i32) {
        if let Some(unwrapped_node) = node {
            let left = unwrapped_node.borrow_mut().left.take();
            let right = unwrapped_node.borrow_mut().right.take();
            let value = unwrapped_node.borrow().val;
            let good_node = value >= max;
            if good_node {
                ret.push(0);
            }
            dfs(left, ret, if good_node { value } else { max });
            dfs(right, ret, if good_node { value } else { max });
        }
    }
    let mut ret = vec![];
    dfs(root, &mut ret, i32::MIN);
    ret.len() as i32
}

总结

在遍历过程中，如果有需要统计的值，最好用引用对象去传递。