tree Archives - Page 7 of 21 - Huahua's Tech Road

花花酱 LeetCode 1302. Deepest Leaves Sum

By zxi on January 31, 2020

Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Solution 1: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int deepestLeavesSum(TreeNode* root) {

int sum = 0;

int max_depth = 0;

function<void(TreeNode*, int)> dfs = [&](TreeNode* n, int d) {

if (!n) return;

if (d > max_depth) {

max_depth = d;

sum = 0;

}

if (d == max_depth) sum += n->val;

dfs(n->left, d + 1);

dfs(n->right, d + 1);

};

dfs(root, 0);

return sum;

}

};

花花酱 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

By zxi on January 29, 2020

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the BST.

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (p->val < root->val && q->val < root->val)

return lowestCommonAncestor(root->left, p, q);

if (p->val > root->val && q->val > root->val)

return lowestCommonAncestor(root->right, p, q);

return root;

}

};

花花酱 LeetCode 257. Binary Tree Paths

By zxi on January 29, 2020

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution: Recursion

Time complexity: O(n)
Space complexity: O(n) / output can be O(n^2)

C++

// Author: Huahua

class Solution {

public:

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> ans;

string s;

function<void(TreeNode*, int)> preorder = [&](TreeNode* node, int l) {

if (!node) return;

s += (l > 0 ? "->" : "") + to_string(node->val);

if (!node->left && !node->right)

ans.push_back(s);

preorder(node->left, s.size());

preorder(node->right, s.size());

while (s.size() != l) s.pop_back();

};

preorder(root, 0);

return ans;

}

};

花花酱 LeetCode 107. Binary Tree Level Order Traversal II

By zxi on January 29, 2020

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> levelOrderBottom(TreeNode *root) {

vector<vector<int>> ans;

levelOrderBottom(root, 0, ans);

reverse(ans.begin(), ans.end());

return ans;

}

private:

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

if (!root) return;

while (ans.size() <= depth) ans.push_back({});

ans[depth].push_back(root->val);

levelOrderBottom(root->left, depth + 1, ans);

levelOrderBottom(root->right, depth + 1, ans);

}

};

花花酱 LeetCode 144. Binary Tree Preorder Traversal

By zxi on January 29, 2020

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

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

Solution 1: Recursion

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*)> preorder = [&](TreeNode* n) {

if (!n) return;

ans.push_back(n->val);

preorder(n->left);

preorder(n->right);

};

preorder(root);

return ans;

}

};

Solution 2: Stack

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

C++

// Author: Huahua

class Solution {

public:

vector<int> preorderTraversal(TreeNode* root) {

vector<int> ans;

stack<TreeNode*> s;

if (root) s.push(root);

while (!s.empty()) {

TreeNode* n = s.top();

ans.push_back(n->val);

s.pop();

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

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

}

return ans;

}

Posts tagged as “tree”

花花酱 LeetCode 1302. Deepest Leaves Sum

Solution 1: Recursion

C++

花花酱 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

Solution: Recursion

C++

花花酱 LeetCode 257. Binary Tree Paths

Solution: Recursion

C++

花花酱 LeetCode 107. Binary Tree Level Order Traversal II

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 144. Binary Tree Preorder Traversal

Solution 1: Recursion

C++

Solution 2: Stack

C++