Showing posts with label Tree - Modification. Show all posts

LeetCode 1038 - Binary Search Tree to Greater Sum Tree

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

As a reminder, a binary search tree is a tree that satisfies these constraints:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Note:

The number of nodes in the tree is between 1 and 100.
Each node will have value between 0 and 100.
The given tree is a binary search tree.

X. Reverse Order Traverse
https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/discuss/286725/JavaC%2B%2BPython-Revered-Inorder-Traversal

We need to do the work from biggest to smallest, right to left.
pre will record the previous value the we get, which the total sum of bigger values.
For each node, we update root.val with root.val + pre.

    int pre = 0;
    public TreeNode bstToGst(TreeNode root) {
        if (root.right != null) bstToGst(root.right);
        pre = root.val = pre + root.val;
        if (root.left != null) bstToGst(root.left);
        return root;
    }

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/discuss/286906/Java-3-iterative-and-recursive-codes-w-comments-and-explanation.

Method 1:

Iterative version: use stack to pop out the nodes in reversed in order sequence.

Initially, use cur to point to the root,

push into Stack the right-most path of current subtree;
pop out a node, update sum and the node value;
point cur to the node's left child, if any;
Repeat the above till the stack is empty and cur has no left child.

    public TreeNode bstToGst(TreeNode root) {
        Deque<TreeNode> stk = new ArrayDeque<>();
        TreeNode cur = root;
        int sum = 0;
        while (cur != null || !stk.isEmpty()) {
            while (cur != null) { // save right-most path of the current subtree
                stk.push(cur);
                cur = cur.right;
            }
            cur = stk.pop(); // pop out by reversed in-order.
            sum += cur.val; // update sum.
            cur.val = sum; // update node value.
            cur = cur.left; // move to left branch.
        }    
        return root;
    }

Analysis:

Time & space: O(n).

Method 2:

Recursive version: using a sum TreeNode (more safety) instead of an instance variable.

Obviously, sum updates its value by reversed in-order traversal of nodes.

    public TreeNode bstToGst(TreeNode root) {
        reversedInorder(root, new TreeNode(0));
        return root;
    }
    private void reversedInorder(TreeNode node, TreeNode sum) {
        if (node == null) { return; }
        reversedInorder(node.right, sum);
        sum.val += node.val;
        node.val = sum.val;
        reversedInorder(node.left, sum);
    }

Analysis:

Time: O(n), space: O(n) if considering recursion stack.

Method 3:

Iterative version.

Morris algorithm - for pictures and explanation in details please refer to here.

Note: typically the description of Morris algorithm is about in-order traversal, not reversed in-order. So I add comments for the following code to make beginners more comfortable, hopefully.

    public TreeNode convertBST(TreeNode root) {
        TreeNode cur = root;
        int sum = 0;
        while (cur != null) {
            if (cur.right != null) { // traverse right subtree.
                TreeNode leftMost = cur.right;
                while (leftMost.left != null && leftMost.left != cur) { // locate the left-most node of cur's right subtree.
                    leftMost = leftMost.left;
                }
                if (leftMost.left == null) { // never visit the left-most node yet.
                    leftMost.left = cur; // construct a way back to cur.
                    cur = cur.right; // explore right.
                }else { // visited leftMost already, which implies now on way back.
                    leftMost.left = null; // cut off the fabricated link.
                    sum += cur.val; // update sum.
                    cur.val = sum; // update node value.
                    cur = cur.left; // continue on way back.
                }
            }else { // no right child: 1) cur is the right-most of unvisited nodes; 2) must traverse left.
                sum += cur.val; // update sum.
                cur.val = sum; // update node value.
                cur = cur.left; // continue on way back.
            }
        }
        return root;
    }

二叉树删除边

https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit#heading=h.jb1562yh5s6d

2. 二叉树删除边 (高频 13次)

LC684，BT删除多余边

思路：

684是无向图，用union find，遍历edge，每次把parent付给做节点，若发现母节点相同则为多余
http://massivealgorithms.blogspot.com/2018/05/leetcode-684-redundant-connection.html
685 三种错误情况，multiple parents，cycle， both 在both的情况下仔细讨论删除第一个指向multiple parent的node
http://massivealgorithms.blogspot.com/2018/12/leetcode-685-redundant-connection-ii.html
685 有很多隐含条件：比如 cycle 最多只可能有一个， multiple parents 最多两个，没有multiple parents 的话就一定有cycle, 这样就多了很多限制，分情况讨论的时候就会简单许多。

3 invalid situations

case1: 2 parents no circle

case2: 2 parents with circle

case3: 1 parent with circle

2 main steps

1 check whether there exists a node with 2 parents, if yes, store the two edges.

2 if no edge yielded from step 1, apply union-find and find the edge creating cycle (same as 684); ELSE, apply union-find to ALL edges EXCEPT edges from step 1, then check: if edge 1 from step 1 creates a cycle, return edge 1; else return edge 2.

//请问有的题是binary tree删多余边，这时候输入是 root 还是 edge list ?

Follow up: 给一棵二叉搜索树，有一条多余边，删除它

例子：

/ \

5 9

/ \ /

3 8

对于多余边5-8，9-8此处的删除需要有选择，跟之前的题目找到多余边立马不分选择删除有区别

思路: LC 98: Validate Binary Search Tree

DFS，参数中带着左右边界，返回值为新树的根节点，如果当前节点不在当前树的范围内，返回null删除该边

参考代码

provider: null

public void deleteEdge(TreeNode root) {

if(root == null) return;

root = dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

private TreeNode dfs(TreeNode root, int left, int right) {

if(root == null) return null;

if(root.val <= left || root.val >= right) return null;

root.left = dfs(root.left, left, root.val);

root.right = dfs(root.right, root.val, right);

return root;

}

能否说一句无关的废话，上面BST删除多余的edge的思路，和BST insert以及delete node的思路很类似，可以放到一起总结复习。(Editor: 嗯，思路差不多，但是follow up用DFS感觉好做一点，第一题UF和DFS都能做)

CPP参考代码：

(Provider: Anonym)

void isValidBST(TreeNode* root) {

root=isValidBST(root, nullptr, nullptr);

}

TreeNode* isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {

if(!root) return nullptr;

if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)

return nullptr;

root->left = isValidBST(root->left, minNode, root);

root->right = isValidBST(root->right, root, maxNode);

return root;

}

LeetCode 998 - Maximum Binary Tree II

We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.

Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine:

If A is empty, return null.
Otherwise, let A[i] be the largest element of A. Create a root node with value A[i].
The left child of root will be Construct([A[0], A[1], ..., A[i-1]])
The right child of root will be Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
Return root.

Note that we were not given A directly, only a root node root = Construct(A).

Suppose B is a copy of A with the value val appended to it. It is guaranteed that B has unique values.

Return Construct(B).

Example 1:

Input: root = [4,1,3,null,null,2], val = 5
Output: [5,4,null,1,3,null,null,2]
Explanation: A = [1,4,2,3], B = [1,4,2,3,5]

https://leetcode.com/problems/maximum-binary-tree-ii/discuss/242936/JavaC%2B%2BPython-Recursion-and-Iteration

If root.val > val, recusion on the right.
Else, put right subtree on the left of new node TreeNode(val)

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root != null && root.val > val) {
            root.right = insertIntoMaxTree(root.right, val);
            return root;
        }
        TreeNode node = new TreeNode(val);
        node.left = root;
        return node;
    }

https://leetcode.com/problems/maximum-binary-tree-ii/discuss/242897/Java-clean-recursive-solution

The idea is to insert node to the right parent or right sub-tree of current node. Using recursion can achieve this:
If inserted value is greater than current node, the inserted goes to right parent
If inserted value is smaller than current node, we recursively re-cauculate right subtree

    public TreeNode insertIntoMaxTree(TreeNode root, int v) {
        if(root==null)return new TreeNode(v);
        if(root.val<v){
            TreeNode node = new TreeNode(v);
            node.left=root;
            return node;
        }
        root.right=insertIntoMaxTree(root.right,v);
        return root;
    }

https://leetcode.com/problems/maximum-binary-tree-ii/discuss/243188/How-many-people-can't-understand-what-the-question-means

我解释下为什么当val<root.val时，是往右边加的。
1. the given tree was constructed from an list A (root = Construct(A)). So, List<Integer> A = new ArrayList();
2. Suppose B is a copy of A with the value val appended to it. So, B = new ArrayList(A) and B.add(val);
3. The left child of root will be Construct([A[0], A[1], ..., A[i-1]]), 
The right child of root will be Construct([A[i+1], A[i+2], ..., A[A.length - 1]]).
in this case A represent B, B[B.length-1] = val, So.
4. If val is the largest, i = B.length-1, the root node's value is val, i=0 to i-1 are in the left child of root. 
This explains why when val > root.val, root should be the left child of new node with value val.
5. Else val is not the largest, the new node with value val is always the right child of root.

X. Solution 2: Iteration

Search on the right, find the node that cur.val > val > cur.right.val
Then create new node TreeNode(val),
put old cur.right as node.left,
put node as new cur.right.

    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        TreeNode node = new TreeNode(val), cur = root;
        if (root.val < val) {
            node.left = root;
            return node;
        }
        while (cur.right != null && cur.right.val > val) {
            cur = cur.right;
        }
        node.left = cur.right;
        cur.right = node;
        return root;
    }