Posts tagged as “binary tree”

花花酱 LeetCode 3319. K-th Largest Perfect Subtree Size in Binary Tree

By zxi on October 12, 2024

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the k^th largest perfect binary

subtree, or -1 if it doesn’t exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2^nd largest size is 3.

Example 2:

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

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

The number of nodes in the tree is in the range [1, 2000].
1 <= Node.val <= 2000
1 <= k <= 1024

Solution: DFS

Write a function f() to return the perfect subtree size at node n.

def f(TreeNode n):
if not n: return 0
l, r = f(n.left), f(n.right)
return l + r + 1 if l == r && l != -1 else -1

Time complexity: O(n + KlogK)
Space complexity: O(n)

class Solution {

public:

int kthLargestPerfectSubtree(TreeNode* root, int k) {

vector<int> ss;

function<int(TreeNode*)> PerfectSubtree = [&](TreeNode* node) -> int {

if (node == nullptr) return 0;

int l = PerfectSubtree(node->left);

int r = PerfectSubtree(node->right);

if (l == r && l != -1) {

ss.push_back(l + r + 1);

return ss.back();

}

return -1;

};

PerfectSubtree(root);

sort(rbegin(ss), rend(ss));

return k <= ss.size() ? ss[k - 1] : -1;

}

};

花花酱 LeetCode 1361. Validate Binary Tree Nodes

By zxi on February 23, 2020

You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Example 4:

Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
Output: false

Constraints:

1 <= n <= 10^4
leftChild.length == rightChild.length == n
-1 <= leftChild[i], rightChild[i] <= n - 1

Solution: Count in-degrees for each node

in degree must <= 1 and there must be exact one node that has 0 in-degree.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {

vector<int> in(n);

for (int l : leftChild) if (l >= 0) ++in[l];

for (int r : rightChild) if (r >= 0) ++in[r];

int zero = 0;

for (int i = 0; i < n; ++i) {

if (in[i] > 1) return false;

if (in[i] == 0) ++zero;

}

// # of nodes without parent must be 1.

return zero == 1;

}

};

花花酱 LeetCode 337. House Robber III

By zxi on March 15, 2018

题目大意：给你一棵二叉树，不能同时取两个相邻的节点(parent/child)，问最多能取得的节点的值的和是多少。

Problem:

https://leetcode.com/problems/house-robber-iii/description/

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Maximum amount of money the thief can rob = 4 + 5 = 9.

Idea:

Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)

Solution 1: Recursion w/o memorization

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 1289 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

};

Solution 2: Recursion w/ memorization

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int rob(TreeNode* root) {

if (root == nullptr) return 0;

if (m_.count(root)) return m_[root];

int val = root->val;

int ll = root->left ? rob(root->left->left) : 0;

int lr = root->left ? rob(root->left->right) : 0;

int rl = root->right ? rob(root->right->left) : 0;

int rr = root->right ? rob(root->right->right) : 0;

return m_[root] = max(val + ll + lr + rl + rr, rob(root->left) + rob(root->right));

}

private:

unordered_map<TreeNode*, int> m_;

};

Solution 3: Recursion return children’s value

// Author: Huahua

// Running time: 10 ms (beats 97.57%)

class Solution {

public:

int rob(TreeNode* root) {

int l = 0;

int r = 0;

return rob(root, l, r);

}

private:

// return rob(root) and stores rob(root->left/right) in l/r.

int rob(TreeNode* root, int& l, int& r) {

if (root == nullptr) return 0;

int ll = 0;

int lr = 0;

int rl = 0;

int rr = 0;

l = rob(root->left, ll, lr);

r = rob(root->right, rl, rr);

return max(root->val + ll + lr + rl + rr, l + r);

}

};

Python3

"""

Author: Huahua

Running time: 64 ms (beats 93.18%)

"""

class Solution:

def rob(self, root):

def rob(root):

if not root: return 0, 0, 0

l, ll, lr = rob(root.left)

r, rl, rr = rob(root.right)

return max(root.val + ll + lr + rl + rr, l + r), l, r

return rob(root)[0]

Related Problems:

花花酱 LeetCode 198. House Robber

花花酱 LeetCode 145. Binary Tree Postorder Traversal

By zxi on September 8, 2017

Problem:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Solution 1:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

vector<int> ans;

postorderTraversal(root, ans);

return ans;

}

void postorderTraversal(TreeNode* root, vector<int>& ans) {

if (!root) return;

postorderTraversal(root->left, ans);

postorderTraversal(root->right, ans);

ans.push_back(root->val);

}

};

Solution 2:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

vector<int> ans;

const vector<int> l = postorderTraversal(root->left);

const vector<int> r = postorderTraversal(root->right);

ans.insert(ans.end(), l.begin(), l.end());

ans.insert(ans.end(), r.begin(), r.end());

ans.push_back(root->val);

return ans;

}

};

Solution 3:

// Author: Huahua

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

if (!root) return {};

deque<int> ans;

stack<TreeNode*> s;

s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

s.pop();

ans.push_front(n->val); // O(1)

if (n->left) s.push(n->left);

if (n->right) s.push(n->right);

}

return vector<int>(ans.begin(), ans.end());

}

};

花花酱 LeetCode 637. Average of Levels in Binary Tree

By zxi on September 7, 2017

Problem:

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:

/ \

9 20

/ \

15 7

Output: [3, 14.5, 11]

Explanation:

The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.

Hence return [3, 14.5, 11].

Time Complexity:

O(n)

Space Complexity:

O(h)

Solution 1:

BFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<double> ans;

vector<TreeNode*> curr, next;

curr.push_back(root);

// process every level one by one

while(!curr.empty()) {

long long sum = 0;

for(const auto& node : curr) {

sum += node->val;

if (node->left) next.push_back(node->left);

if (node->right) next.push_back(node->right);

}

ans.push_back(static_cast<double>(sum) / curr.size());

curr.swap(next);

next.clear();

}

return ans;

}

};

Solution 2:

DFS

// Author: Huahua

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

if(root == nullptr) return {};

vector<pair<long long, int>> sum_count;

vector<double> ans;

preorder(root, 0, sum_count);

for(const auto& p : sum_count)

ans.push_back(static_cast<double>(p.first) / p.second);

return ans;

}

private:

void preorder(TreeNode* root, int depth, vector<pair<long long, int>>& sum_count) {

if(root == nullptr) return;

if(depth>=sum_count.size()) sum_count.push_back({0,0});

sum_count[depth].first += root->val;

++sum_count[depth].second;

preorder(root->left, depth+1, sum_count);

preorder(root->right, depth+1, sum_count);

}

};

Related Problems:

[解题报告] LeetCode 102. Binary Tree Level Order Traversal