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

超、凢脫俗 2022-10-07 13:55 2阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/count-good-nodes-in-binary-tree/][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:**

![353481f2e6499ab0d25d68faf695dff4.png][]

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:**

![6a961acb6d9820da72043a0cbeb4e634.png][]

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)));
    	}
    }

[https_leetcode.com_problems_count-good-nodes-in-binary-tree]: https://leetcode.com/problems/count-good-nodes-in-binary-tree/
[353481f2e6499ab0d25d68faf695dff4.png]: /images/20221005/25f28bb8753e412c87b0b62a30a03491.png
[6a961acb6d9820da72043a0cbeb4e634.png]: /images/20221005/ff83ceb0c97c40218b9162a9781522dd.png