LeetCode - Medium - 1448. Count Good Nodes in Binary Tree-蒲公英云

LeetCode - Medium - 1448. Count Good Nodes in Binary Tree

Topic

Tree
Depth-first Search

Description

https://leetcode.com/problems/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.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

The number of nodes in the binary tree is in the range [ 1 , 1 0 5 ] [1, 10^5] [1,105].
Each node’s value is between [ − 1 0 4 , 1 0 4 ] [-10^4, 10^4] [−104,104].

Analysis

方法一：递归版DFS

方法二：迭代版DFS

Submission

import java.util.LinkedList;
import com.lun.util.BinaryTree.TreeNode;
public class CountGoodNodesInBinaryTree { 
    //方法一：递归版
    public int goodNodes(TreeNode root) { 
        return goodNodes(root, Integer.MIN_VALUE);
    }
    public int goodNodes(TreeNode node, int max) { 
        if(node == null) return 0;
        int nextMax = Math.max(max, node.val);
        return (node.val >= max ? 1 : 0) + goodNodes(node.left, nextMax)// 
                + goodNodes(node.right, nextMax);
    }
    //方法二：迭代版
    public int goodNodes2(TreeNode root) { 
        if(root == null)
            return 0;
        int result = 0;
        LinkedList<Object[]> stack = new LinkedList<>(); 
        stack.add(new Object[] { root, Integer.MIN_VALUE});
        while(!stack.isEmpty()) { 
            Object[] arr = stack.pop();
            TreeNode node = (TreeNode)arr[0];
            int max = (int)arr[1];
            if(node.val >= max)
                result++;
            int nextMax = Math.max(max, node.val);
            if(node.right != null)
                stack.push(new Object[] { node.right, nextMax});
            if(node.left != null)
                stack.push(new Object[] { node.left, nextMax});
        }
        return result;
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
import com.lun.util.BinaryTree;
public class CountGoodNodesInBinaryTreeTest { 
    @Test
    public void test() { 
        CountGoodNodesInBinaryTree obj = new CountGoodNodesInBinaryTree();
        assertEquals(4, obj.goodNodes(BinaryTree.integers2BinaryTree(3, 1, 4, 3, null, 1, 5)));
        assertEquals(3, obj.goodNodes(BinaryTree.integers2BinaryTree(3, 3, null, 4, 2)));
        assertEquals(1, obj.goodNodes(BinaryTree.integers2BinaryTree(1)));
    }
    @Test
    public void test2() { 
        CountGoodNodesInBinaryTree obj = new CountGoodNodesInBinaryTree();
        assertEquals(4, obj.goodNodes2(BinaryTree.integers2BinaryTree(3, 1, 4, 3, null, 1, 5)));
        assertEquals(3, obj.goodNodes2(BinaryTree.integers2BinaryTree(3, 3, null, 4, 2)));
        assertEquals(1, obj.goodNodes2(BinaryTree.integers2BinaryTree(1)));
    }
}