Skip to content

1448. Count Good Nodes in Binary Tree

SourceBiweekly Contest 26 Q3DifficultyMediumRating1360

Description

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, 10^5].
  • Each node's value is between [-10^4, 10^4].

Solutions

Solution 1

Thinking

A node is good if nothing larger appears on the path from the root. \(n\le 10^5\). DFS carries the path maximum \(mx\); count the node when its value is at least \(mx\), then update \(mx\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, mx: int):
            if root is None:
                return
            nonlocal ans
            if mx <= root.val:
                ans += 1
                mx = root.val
            dfs(root.left, mx)
            dfs(root.right, mx)

        ans = 0
        dfs(root, -1000000)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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 {
    private int ans = 0;

    public int goodNodes(TreeNode root) {
        dfs(root, -100000);
        return ans;
    }

    private void dfs(TreeNode root, int mx) {
        if (root == null) {
            return;
        }
        if (mx <= root.val) {
            ++ans;
            mx = root.val;
        }
        dfs(root.left, mx);
        dfs(root.right, mx);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int goodNodes(TreeNode* root) {
        int ans = 0;
        function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int mx) {
            if (!root) {
                return;
            }
            if (mx <= root->val) {
                ++ans;
                mx = root->val;
            }
            dfs(root->left, mx);
            dfs(root->right, mx);
        };
        dfs(root, -1e6);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func goodNodes(root *TreeNode) (ans int) {
    var dfs func(*TreeNode, int)
    dfs = func(root *TreeNode, mx int) {
        if root == nil {
            return
        }
        if mx <= root.Val {
            ans++
            mx = root.Val
        }
        dfs(root.Left, mx)
        dfs(root.Right, mx)
    }
    dfs(root, -10001)
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function goodNodes(root: TreeNode | null): number {
    let ans = 0;
    const dfs = (root: TreeNode | null, mx: number) => {
        if (!root) {
            return;
        }
        if (mx <= root.val) {
            ++ans;
            mx = root.val;
        }
        dfs(root.left, mx);
        dfs(root.right, mx);
    };
    dfs(root, -1e6);
    return ans;
}

Solution 2: Explicit Stack

Thinking

A node is good when no larger value appears on the path from the root. With \(n\) up to \(10^5\), one walk that carries the path maximum \(mx\) is enough: count the node when its value is at least \(mx\), then update \(mx\).

The walk enters the left child first. A left chain can be \(n\) nodes long, so recursion overflows before the count is finished. Each node is compared only with the maximum on its own path, so the two children do not depend on each other.

The nodes still to visit fit on an explicit stack together with the \(mx\) from above. After a pop, a value at least \(mx\) is counted and \(mx\) becomes that value; the right child is pushed, then the left child, both with this \(mx\), so the left child is handled first.

The initial \(mx\) is below the lower bound \(-10^4\), so the root is always good. Each node is pushed once.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        ans = 0
        stk = [(root, -1000000)]
        while stk:
            node, mx = stk.pop()
            if node is None:
                continue
            if mx <= node.val:
                ans += 1
                mx = node.val
            stk.append((node.right, mx))
            stk.append((node.left, mx))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 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 ans = 0;
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> limits = new ArrayDeque<>();
        if (root != null) {
            nodes.push(root);
            limits.push(-100000);
        }
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int mx = limits.pop();
            if (mx <= node.val) {
                ++ans;
                mx = node.val;
            }
            if (node.right != null) {
                nodes.push(node.right);
                limits.push(mx);
            }
            if (node.left != null) {
                nodes.push(node.left);
                limits.push(mx);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int goodNodes(TreeNode* root) {
        int ans = 0;
        vector<pair<TreeNode*, int>> stk;
        stk.emplace_back(root, -1000000);
        while (!stk.empty()) {
            auto [node, mx] = stk.back();
            stk.pop_back();
            if (!node) {
                continue;
            }
            if (mx <= node->val) {
                ++ans;
                mx = node->val;
            }
            stk.emplace_back(node->right, mx);
            stk.emplace_back(node->left, mx);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func goodNodes(root *TreeNode) (ans int) {
    stk := []struct {
        node *TreeNode
        mx   int
    }{{root, -10001}}
    for len(stk) > 0 {
        cur := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        node, mx := cur.node, cur.mx
        if node == nil {
            continue
        }
        if mx <= node.Val {
            ans++
            mx = node.Val
        }
        stk = append(stk, struct {
            node *TreeNode
            mx   int
        }{node.Right, mx}, struct {
            node *TreeNode
            mx   int
        }{node.Left, mx})
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function goodNodes(root: TreeNode | null): number {
    let ans = 0;
    const stk: [TreeNode | null, number][] = [[root, -1e6]];
    while (stk.length) {
        const [node, limit] = stk.pop()!;
        if (!node) {
            continue;
        }
        let mx = limit;
        if (mx <= node.val) {
            ++ans;
            mx = node.val;
        }
        stk.push([node.right, mx]);
        stk.push([node.left, mx]);
    }
    return ans;
}

Comments