tree Archives - Page 9 of 20 - Huahua's Tech Road

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

By zxi on October 3, 2019

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

Solution: Recursion

Similar to LC 105

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

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[postorder[pe]];

int pm = ps + (im - is) - 1;

auto root = new TreeNode(postorder[pe]);

root->left = buildTree(is, im - 1, ps, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe - 1);

return root;

};

return buildTree(0, inorder.size() - 1, 0, postorder.size() - 1);

}

};

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

By zxi on October 3, 2019

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

Solution: Recursion

Preprocessing: use a hashtable to store the index of element in preorder array.

For an element in inorder array, find the pos of it in preorder array in O(1), anything to the left will be the leftchild and anything to the right will be the right child.

e.g.
buildTree([9, 3, 15, 20, 7], [3, 9, 20, 15, 7]):
root = TreeNode(9) # inorder[0] = 9
root.left = buildTree([3], [3])
root.right = buildTree([15, 20, 7], [20, 15, 7])
return root

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

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[preorder[ps]];

int pm = ps + (im - is);

auto root = new TreeNode(preorder[ps]);

root->left = buildTree(is, im - 1, ps + 1, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe);

return root;

};

return buildTree(0, inorder.size() - 1, 0, preorder.size() - 1);

}

};

花花酱 LeetCode 99. Recover Binary Search Tree

By zxi on September 29, 2019

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

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

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

Solution: Inorder traversal

Using inorder traversal to find two nodes that have val < prev.val

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

C++

// Author: Huahua

class Solution {

public:

void recoverTree(TreeNode *root) {

inorder(root);

swap(first->val, second->val);

}

void inorder(TreeNode* root) {

if (!root) return;

inorder(root->left);

if (prev && prev->val > root->val) {

if (!first) first = prev;

second = root;

}

prev = root;

inorder(root->right);

}

private:

TreeNode* first;

TreeNode* second;

TreeNode* prev;

};

花花酱 LeetCode 96. Unique Binary Search Trees

By zxi on September 29, 2019

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution: DP

dp[i] = sum(dp[j] * dp[i – j – 1]) (0 <= j < i )

root: 1 node
left child: j nodes
right child i – j – 1 nodes

try all possible partitions

ans = dp[n]

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

C++

// Author: Huahua

class Solution {

public:

int numTrees(int n) {

vector<int> dp(n + 1);

dp[0] = 1;

for (int i = 1; i <= n; i++)

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

dp[i] += dp[j] * dp[i - j - 1];

return dp[n];

}

};

花花酱 LeetCode 116. Populating Next Right Pointers in Each Node

By zxi on August 22, 2019

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.

Solution: Recursion

Do a preorder traversal:
1. return if self is empty or leaf
2. self.left->next = self.right
3. if self.next: self.right.next = self.next.left

Time complexity: O(n)
Space complexity: O(log(n)) since it’s a perfect tree

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

if (!root || !root->left) return root;

root->left->next = root->right;

if (root->next)

root->right->next = root->next->left;

connect(root->left);

connect(root->right);

return root;

}

};

Posts tagged as “tree”

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 99. Recover Binary Search Tree

Solution: Inorder traversal

C++

花花酱 LeetCode 96. Unique Binary Search Trees

Solution: DP

C++

花花酱 LeetCode 116. Populating Next Right Pointers in Each Node

Solution: Recursion

C++