Count Good Nodes in Binary Tree

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.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
           

思路：記住：tree的題，隻有兩種解法，1: traverse 2. Divide & Conquer.這題需要從上往下傳遞目前的最大值；注意傳值，除了method return value之外，還可以參數傳值；要連續遞增的，那麼也就是走到目前最大的值比root小就可以；把目前遇到的最大值往下傳就可以；

錯誤點：傳值，除了method遞歸傳值，參數也可以傳值；

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int goodNodes(TreeNode root) {
        int[] res = {0};
        int prevalue = root.val;
        goodNodesHelper(root, res, prevalue);
        return res[0];
    }
    
    private void goodNodesHelper(TreeNode root, int[] res, int prevalue) {
        if(root == null) {
            return;
        }
        if(root.val >= prevalue) {
            prevalue = root.val;
            res[0]++;
        }
        goodNodesHelper(root.left, res, prevalue);
        goodNodesHelper(root.right, res, prevalue);
    }
}