Posts tagged as “tree”

花花酱 LeetCode 236. Lowest Common Ancestor of a Binary Tree

By zxi on September 14, 2018

Problem

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

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 the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Example 1:

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

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, 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 binary tree.

Solution 1: Recursion

Time complexity: O(n)

Space complexity: O(h)

For a given root, recursively call LCA(root.left, p, q) and LCA(root.right, p, q)

if both returns a valid node which means p, q are in different subtrees, then root will be their LCA.

if only one valid node returns, which means p, q are in the same subtree, return that valid node as their LCA.

C++

// Author: Huahua

class Solution {

public:

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

if (!root || root == p || root == q) return root;

TreeNode* l = lowestCommonAncestor(root->left, p, q);

TreeNode* r = lowestCommonAncestor(root->right, p, q);

if (l && r) return root;

return l ? l : r;

}

};

Java

// Author: Huahua

class Solution {

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

if (root == null || root == p || root == q) return root;

TreeNode l = lowestCommonAncestor(root.left, p, q);

TreeNode r = lowestCommonAncestor(root.right, p, q);

if (l == null || r == null) return l == null ? r : l;

return root;

}

Python3

# Author: Huahua

class Solution:

def lowestCommonAncestor(self, root, p, q):

if any((not root, root == p, root == q)): return root

l = self.lowestCommonAncestor(root.left, p, q)

r = self.lowestCommonAncestor(root.right, p, q)

if not l or not r: return l if l else r

return root

Problem

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

Note:

The number of nodes in the given tree will be between 1 and 100.
Each node will have a unique integer value from 0 to 1000.

Solution: In-order traversal

root = 5

inorder(root.left) 之后

self.prev = 4

（1-4）已经处理完了，这时候的树是很奇怪的一个形状，3即是2的右子树，又是5的左子树。

2 5

\ / \

3 6

\ \

prev -> 4 8

/ \

7 9

—————————

5.left = None # 把5->3的链接断开

/ \

7 9

—————————–

self.prev.right = root <=> 4.right = 5

把5接到4的右子树

5 <– prev

/ \

7 9

self.prev = root <=> prev = 5

inorder(5.right) <=> inorder(6) 然后再去递归处理6（及其子树）即可。

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 64 ms

class Solution {

public:

TreeNode* increasingBST(TreeNode* root) {

TreeNode dummy(0);

prev_ = &dummy;

inorder(root);

return dummy.right;

}

private:

TreeNode* prev_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

prev_->right = root;

prev_ = root;

prev_->left = nullptr;

inorder(root->right);

}

};

Java

class Solution {

private TreeNode prev;

public TreeNode increasingBST(TreeNode root) {

TreeNode dummy = new TreeNode(0);

this.prev = dummy;

inorder(root);

return dummy.right;

}

private void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

this.prev.right = root;

this.prev = root;

this.prev.left = null;

inorder(root.right);

}

Python3

class Solution:

def increasingBST(self, root):

dummy = TreeNode(0)

self.prev = dummy

def inorder(root):

if not root: return None

inorder(root.left)

root.left = None

self.prev.right = root

self.prev = root

inorder(root.right)

inorder(root)

return dummy.right

花花酱 LeetCode 894. All Possible Full Binary Trees

By zxi on August 26, 2018

Problem

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

Note:

1 <= N <= 20

Solution: Recursion

Key observations:

n must be odd, If n is even, no possible trees
ans is the cartesian product of trees(i) and trees(n-i-1). Ans = {Tree(0, l, r) for l, r in trees(i) X trees(N – i – 1)}.

w/o cache

C++

// Author: Huahua

// Running time: 72 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 20 ms

class Solution {

public List<TreeNode> allPossibleFBT(int N) {

List<TreeNode> ans = new ArrayList<>();

if (N % 2 == 0) return ans;

if (N == 1) {

ans.add(new TreeNode(0));

return ans;

}

for (int i = 1; i < N; i += 2) {

for (TreeNode l : allPossibleFBT(i))

for (TreeNode r : allPossibleFBT(N - i - 1)) {

TreeNode root = new TreeNode(0);

root.left = l;

root.right = r;

ans.add(root);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 396 ms

"""

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

ans = []

for i in range(1, N, 2):

for l in self.allPossibleFBT(i):

for r in self.allPossibleFBT(N - i - 1):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

return ans

w/cache

C++

// Author: Huahua

// Running time: 68 ms

static constexpr int kMaxN = 20 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Python

using itertools.product w/ cache

"""

Author: Huahua

Running time: 188 ms

"""

m = [[] for _ in range(21)]

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

if len(m[N]) > 0: return m[N]

ans = []

for i in range(1, N, 2):

for l, r in itertools.product(self.allPossibleFBT(i),

self.allPossibleFBT(N - i - 1)):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

m[N] = ans

return ans

C++

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

vector<vector<TreeNode*>> dp(N + 1);

dp[1] = {new TreeNode(0)};

for (int i = 3; i <= N; i += 2)

for (int j = 1; j < i; j += 2) {

int k = i - j - 1;

for (const auto& l : dp[j])

for (const auto& r : dp[k]) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

dp[i].push_back(root);

}

return dp[N];

}

};

Benchmark

No-cache vs cached

C++

#include <iostream>

#include <vector>

#include <array>

#include <ctime>

#include <cstdio>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

static constexpr int kMaxN = 101 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class NoCache {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

class Cached {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

int main(int argc, char** argv) {

printf("N\tno-cache\tcached\n");

for (int i = 1; i <= 35; i += 2) {

printf("%02d\t", i);

{

auto start = clock();

(void)(NoCache().allPossibleFBT(i));

printf("%8.4f\t", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

{

// Clear the cache.

for (int j = 0; j < kMaxN; ++j)

m[i].clear();

auto start = clock();

(void)(Cached().allPossibleFBT(i));

printf("%8.4f\n", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

return 0;

}

花花酱 LeetCode 112. Path Sum

By zxi on August 25, 2018

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool hasPathSum(TreeNode* root, int sum) {

if (!root) return false;

if (!root->left && !root->right) return root->val==sum;

int new_sum = sum - root->val;

return hasPathSum(root->left, new_sum) || hasPathSum(root->right, new_sum);

}

};

Problem

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

Solution: Recursion

pre = [(root) (left-child) (right-child)]

post = [(left-child) (right-child) (root)]

We need to recursively find the first node in pre.left-child from post.left-child

e.g.

pre = [(1), (2,4,5), (3,6,7)]

post = [(4,5,2), (6,7,3), (1)]

First element of left-child is 2 and the length of it is 3.

root = new TreeNode(1)
root.left = build((2,4,5), (4,5,2))
root.right = build((3,6,7), (6,7,3))

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {

return constructFromPrePost(cbegin(pre), cend(pre), cbegin(post), cend(post));

}

private:

typedef vector<int>::const_iterator VIT;

TreeNode* constructFromPrePost(VIT pre_l, VIT pre_r, VIT post_l, VIT post_r) {

if (pre_l == pre_r) return nullptr;

TreeNode* root = new TreeNode(*pre_l);

++pre_l;

--post_r;

if (pre_l == pre_r) return root;

VIT post_m = next(find(post_l, post_r, *pre_l));

VIT pre_m = pre_l + (post_m - post_l);

root->left = constructFromPrePost(pre_l, pre_m, post_l, post_m);

root->right = constructFromPrePost(pre_m, pre_r, post_m, post_r);

return root;

}

};

Time complexity: O(n^2)

Space complexity: O(n)

"""

Author: Huahua

Running time: 60 ms

"""

class Solution:

def constructFromPrePost(self, pre, post):

def build(i, j, n):

if n <= 0: return None

root = TreeNode(pre[i])

if n == 1: return root

k = j

while post[k] != pre[i + 1]: k += 1

l = k - j + 1

root.left = build(i + 1, j, l)

root.right = build(i + l + 1, k + 1, n - l - 1)

return root

return build(0, 0, len(pre))

Time complexity: O(n)

"""

Author: Huahua

Running time: 52 ms (beats 100%)

"""

class Solution:

def constructFromPrePost(self, pre, post):

def build(i, j, n):

if n <= 0: return None

root = TreeNode(pre[i])

if n == 1: return root

k = index[pre[i + 1]]

l = k - j + 1

root.left = build(i + 1, j, l)

root.right = build(i + l + 1, k + 1, n - l - 1)

return root

index = {}

for i in range(len(pre)):

index[post[i]] = i

return build(0, 0, len(pre))

Posts tagged as “tree”

花花酱 LeetCode 236. Lowest Common Ancestor of a Binary Tree

Problem

Solution 1: Recursion

C++

Java

Python3

Related Problems:

花花酱 LeetCode 897. Increasing Order Search Tree

Problem

Solution: In-order traversal

C++

Java

Python3

花花酱 LeetCode 894. All Possible Full Binary Trees

Problem

Solution: Recursion

C++

Java

Python

C++

Python

C++

Benchmark

C++

花花酱 LeetCode 112. Path Sum

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal

Problem

Solution: Recursion