Post-Order

Post-Order traversals were, to me, the most unintuitive types of traversals because you are performing the induction before the base case, but once you grasp the idea it is very powerful, this problem exemplifies it clearly. Code is down below, cheers, ACC.

Count Dominant Nodes in a Binary Tree - LeetCode

You are given the root of a .

A node x is called dominant if its value is equal to the maximum value among all nodes in the rooted at x.

Return the number of dominant nodes in the tree.

 

Example 1:

Input: root = [5,3,8,2,4,7,1]

Output: 5

Explanation:

• The leaf nodes with values 2, 4, 7, and 1 are dominant.
• The node with value 8 is dominant because its value is the maximum value in its subtree [8, 7, 1].
• Thus, the answer is 5.

Example 2:

Input: root = [1,2,3,1,2]

Output: 4

Explanation:

• The leaf nodes with values 1, 2, and 3 are dominant.
• The node with value 2 whose subtree is [2, 1, 2] is dominant because its value is the maximum value in its subtree.
• Thus, the answer is 4.

 

Constraints:

• The number of nodes in the tree is in the range [1, 105].
• 1 <= Node.val <= 109
• The tree is guaranteed to be a complete binary tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int CountDominantNodes(TreeNode root)
    {
        int max = 0;
        int retVal = 0;
        _CountDominantNodes(root, ref max, ref retVal);

        return retVal;
    }

    private void _CountDominantNodes(TreeNode node,
                                     ref int max,
                                     ref int retVal)
    {
        if (node == null) return;

        int maxLeft = 0;
        _CountDominantNodes(node.left, ref maxLeft, ref retVal);
        int maxRight = 0;
        _CountDominantNodes(node.right, ref maxRight, ref retVal);

        max = node.val;
        max = Math.Max(max, maxLeft);
        max = Math.Max(max, maxRight);

        if (max == node.val)
            retVal++;
    }
}