Posts tagged as “tree”

花花酱 LeetCode 450. Delete Node in a BST

By zxi on March 24, 2018

Problem

https://leetcode.com/problems/delete-node-in-a-bst/description/

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

Solution: Recursion

Time complexity: O(h)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 36 ms

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

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

* };

class Solution {

public:

TreeNode* deleteNode(TreeNode* root, int key) {

if (root == nullptr) return root;

if (key > root->val) {

root->right = deleteNode(root->right, key);

} else if (key < root->val) {

root->left = deleteNode(root->left, key);

} else {

TreeNode* new_root = nullptr;

if (root->left == nullptr) {

new_root = root->right;

} else if (root->right == nullptr) {

new_root = root->left;

} else {

// Find the min node in the right sub tree

TreeNode* parent = root;

new_root = root->right;

while (new_root->left != nullptr) {

parent = new_root;

new_root = new_root->left;

}

if (parent != root) {

parent->left = new_root->right;

new_root->right = root->right;

}

new_root->left = root->left;

}

delete root;

return new_root;

}

return root;

}

};

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

TreeNode* deleteNode(TreeNode* root, int key) {

if (root == nullptr) return root;

if (key > root->val) {

root->right = deleteNode(root->right, key);

} else if (key < root->val) {

root->left = deleteNode(root->left, key);

} else {

if (root->left != nullptr && root->right != nullptr) {

TreeNode* min = root->right;

while (min->left != nullptr) min = min->left;

root->val = min->val;

root->right = deleteNode(root->right, min->val);

} else {

TreeNode* new_root = root->left == nullptr ? root->right : root->left;

root->left = root->right = nullptr;

delete root;

return new_root;

}

return root;

}

};

花花酱 LeetCode 437. Path Sum III

By zxi on March 24, 2018

Problem

题目大意：给你一棵二叉树，返回单向的路径和等于sum的路径数量。

https://leetcode.com/problems/path-sum-iii/description/

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution 1: Recursion

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

int pathSum(TreeNode* root, int sum) {

if (!root) return 0;

return numberOfPaths(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);

}

private:

int numberOfPaths(TreeNode* root, int left) {

if (!root) return 0;

left -= root->val;

return (left == 0 ? 1 : 0) + numberOfPaths(root->left, left) + numberOfPaths(root->right, left);

}

};

Solution 2: Running Prefix Sum

Same idea to 花花酱 LeetCode 560. Subarray Sum Equals K

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 13 ms (beats 97.74%)

public:

int pathSum(TreeNode* root, int sum) {

ans_ = 0;

sums_ = {{0, 1}};

pathSum(root, 0, sum);

return ans_;

}

private:

int ans_;

unordered_map<int, int> sums_;

void pathSum(TreeNode* root, int cur, int sum) {

if (!root) return;

cur += root->val;

ans_ += sums_[cur - sum];

++sums_[cur];

pathSum(root->left, cur, sum);

pathSum(root->right, cur, sum);

--sums_[cur];

}

};

Problem

https://leetcode.com/problems/binary-tree-tilt/description/

题目大意：返回树的总tilt值。对于一个节点的tilt值定义为左右子树元素和的绝对之差。

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

Example:

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

The sum of node values in any subtree won’t exceed the range of 32-bit integer.
All the tilt values won’t exceed the range of 32-bit integer.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTilt(TreeNode* root) {

int sum;

return findTilt(root, sum);

}

private:

// return the total tilt and sum of the root.

int findTilt(TreeNode* root, int& sum) {

if (root == nullptr) return 0;

int ls = 0;

int rs = 0;

int tl = findTilt(root->left, ls);

int tr = findTilt(root->right, rs);

sum = root->val + ls + rs;

return tl + tr + abs(ls - rs);

}

};

v1-2

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTilt(TreeNode* root) {

return findTiltSum(root).first;

}

private:

pair<int, int> findTiltSum(TreeNode* root) {

if (root == nullptr) return {0, 0};

auto l = findTiltSum(root->left);

auto r = findTiltSum(root->right);

return { l.first + r.first + abs(l.second - r.second),

root->val + l.second + r.second };

}

};

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findTilt(TreeNode* root) {

ans_ = 0;

sum(root);

return ans_;

}

private:

int ans_;

int sum(TreeNode* root) {

if (root == nullptr) return 0;

int l = sum(root->left);

int r = sum(root->right);

ans_ += abs(l - r);

return root->val + l + r;

}

};

Python3

"""

Author: Huahua

Running time: 112 ms

"""

class Solution:

def findTilt(self, root):

def findTilt(root):

if not root: return 0, 0

tl, sl = findTilt(root.left)

tr, sr = findTilt(root.right)

return tl + tr + abs(sl - sr), root.val + sl + sr

return findTilt(root)[0]

花花酱 LeetCode 623. Add One Row to Tree

By zxi on March 19, 2018

题目大意：在树的所有第d层位置插入元素v。

Problem

https://leetcode.com/problems/add-one-row-to-tree/description/

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 19 ms (beats 90.85%)

class Solution {

public:

TreeNode* addOneRow(TreeNode* root, int v, int d) {

if (root == nullptr) return nullptr;

// Special case.

if (d == 1) {

TreeNode* new_root = new TreeNode(v);

new_root->left = root;

return new_root;

}

if (d == 2) {

TreeNode* l = root->left;

root->left = new TreeNode(v);

root->left->left = l;

TreeNode* r = root->right;

root->right = new TreeNode(v);

root->right->right = r;

} else {

addOneRow(root->left, v, d - 1);

addOneRow(root->right, v, d - 1);

}

return root;

}

};

花花酱 LeetCode 515. Find Largest Value in Each Tree Row

By zxi on March 5, 2018

题目大意：给你一棵树，返回每一层最大的元素的值。

You need to find the largest value in each row of a binary tree.

Example:

<b>Input:</b>

/ \

3 2

/ \ \

5 3 9

<b>Output:</b> [1, 3, 9]

Solution 1: Inorder traversal + depth info

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> largestValues(TreeNode* root) {

vector<int> ans;

inorder(root, 0, ans);

return ans;

}

private:

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

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back(INT_MIN);

inorder(root->left, d + 1, ans);

ans[d] = max(ans[d], root->val);

inorder(root->right, d + 1, ans);

}

};

Python3

"""

Author: Huahua

Running time: 72 ms (beats 100%)

"""

class Solution:

def largestValues(self, root):

def inorder(root, d, ans):

if not root: return ans

if len(ans) <= d: ans += [float('-inf')]

inorder(root.left, d + 1, ans)

if root.val > ans[d]: ans[d] = root.val

inorder(root.right, d + 1, ans)

return ans

return inorder(root, 0, [])

Posts tagged as “tree”

花花酱 LeetCode 450. Delete Node in a BST

Problem

Solution: Recursion

花花酱 LeetCode 437. Path Sum III

Problem

Example:

Solution 1: Recursion

Solution 2: Running Prefix Sum

Related Problem

花花酱 LeetCode 563. Binary Tree Tilt

Problem

Solution: Recursion

花花酱 LeetCode 623. Add One Row to Tree

Problem

Solution: Recursion

花花酱 LeetCode 515. Find Largest Value in Each Tree Row