LeetCode Solution, Medium, 538. Convert BST to Greater Tree

LeetCode Solution, Medium, 538. Convert BST to Greater Tree

轉換二元搜尋樹成累加樹

Play this article

538. Convert BST to Greater Tree

題目敘述

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

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:

tree.png

Input: root = [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]

Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

Constraints:

  • The number of nodes in the tree is in the range [0, 10**4].
  • 10**4 <= Node.val <= 10**4
  • All the values in the tree are unique.
  • root is guaranteed to be a valid binary search tree.

Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

題目翻譯

這題會給一個二元搜尋樹,然後要從大到小依序的累加。可以看範例一的圖,從 8 一路的累加到 0。

解法解析

這題的解法官方有三種,Recursion、Iteration with a Stack、Morris In-order Traversal。前面兩種時間複雜度跟空間複雜度都一樣是 O(n)。最後一個演算法,可以達到空間複雜度只有 O(1)。但我要吐槽一下,結果我每個程式解答送出後,都是前兩個在前面,有時候真的演算法看看就好,真的還是跑起來才知道呢。

Recursion

這是滿簡單的思維,就是我們用反序的方式遍歷整個二元搜尋樹,然後紀錄每一次的加總並更新節點的值。

Iteration with a Stack

有點算是從 Recursion 而來的想法,首先初始化一個空的 Stack 並把 root 作為當前節點。跟 Recursion 不同的是,我們是透過 Stack 來記住上一個節點。

Morris In-order Traversal

  1. 當節點的右節點為空,代表沒有更大的值,所以處理加總當前節點後去遍歷左節點
  2. 當節點的右節點不為空,代表還有更大的值。找出右節點的最左節點(因為會是當前排序的下一個節點)
    1. 當左節點的不存在,則將其指向當前節點( 代表說反序時,下一個值是目前的節點)
    2. 當左節點存在且跟當前節點不同(因為有可能是上面步驟增加的連結),則將其左節點社為空,並處理當前結點

解法範例

Go

Recursion
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    total := 0
    var convert func(*TreeNode)
    convert = func(node *TreeNode) {
        if node != nil {
            convert(node.Right)
            total += node.Val
            node.Val = total
            convert(node.Left)
        }
    }
    convert(root)
    return root
}
Iteration
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    total := 0
    node := root
    stack := make([]*TreeNode, 0)
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Right
        }

        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        total += node.Val
        node.Val = total
        node = node.Left
    }
    return root
}
Morris Traversal
func getSuccessor(node *TreeNode) *TreeNode {
    succ := node.Right
    for succ.Left != nil && succ.Left != node {
        succ = succ.Left
    }
    return succ
}

func convertBST(root *TreeNode) *TreeNode {
    total := 0
    node := root
    for node != nil {
        if node.Right == nil {
            total += node.Val
            node.Val = total
            node = node.Left
        } else {
            succ := getSuccessor(node)
            if succ.Left == nil {
                succ.Left = node
                node = node.Right
            } else {
                succ.Left = nil
                total += node.Val
                node.Val = total
                node = node.Left
            }
        }
    }
    return root
}

JavaScript

Recursion
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function (root) {
    let total = 0;
    convert(root);

    function convert(root) {
        if (!root) return;
        convert(root.right);
        total += root.val;
        root.val = total;
        convert(root.left);
    }
    return root;
};
Iteration
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function (root) {
    let total = 0,
        node = root;
    const stack = [];
    while (node || stack.length) {
        while (node) {
            stack.push(node);
            node = node.right;
        }

        node = stack.pop();
        total += node.val;
        node.val = total;
        node = node.left;
    }
    return root;
};
Morris Traversal
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function (root) {
    let total = 0,
        node = root;
    while (node) {
        if (!node.right) {
            total += node.val;
            node.val = total;
            node = node.left;
        } else {
            const succ = getSuccessor(node);
            if (succ.left) {
                succ.left = null;
                total += node.val;
                node.val = total;
                node = node.left;
            } else {
                succ.left = node;
                node = node.right;
            }
        }
    }

    return root;
};

const getSuccessor = (node) => {
    let succ = node.right;
    while (succ.left && succ.left !== node) {
        succ = succ.left;
    }
    return succ;
};

Kotlin


PHP


Python

Recursion
class Solution(object):
    def __init__(self):
        self.total = 0

    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is not None:
            self.convertBST(root.right)
            self.total += root.val
            root.val = self.total
            self.convertBST(root.left)
        return root
Iteration
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        total = 0

        node = root
        stack: List[TreeNode] = []
        while stack or node is not None:
            # push all nodes up to (and including) this subtree's maximum on
            # the stack.
            while node is not None:
                stack.append(node)
                node = node.right

            node = stack.pop()
            total += node.val
            node.val = total

            # all nodes with values between the current and its parent lie in
            # the left subtree.
            node = node.left

        return root
Morris Traversal
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Get the node with the smallest value greater than this one.
        def get_successor(node):
            succ = node.right
            while succ.left is not None and succ.left is not node:
                succ = succ.left
            return succ

        total = 0
        node = root
        while node is not None:
            # If there is no right subtree, then we can visit this node and
            # continue traversing left.
            if node.right is None:
                total += node.val
                node.val = total
                node = node.left
            # If there is a right subtree, then there is a node that has a
            # greater value than the current one. therefore, we must traverse
            # that node first.
            else:
                succ = get_successor(node)
                # If there is no left subtree (or right subtree, because we are
                # in this branch of control flow), make a temporary connection
                # back to the current node.
                if succ.left is None:
                    succ.left = node
                    node = node.right
                # If there is a left subtree, it is a link that we created on
                # a previous pass, so we should unlink it and visit this node.
                else:
                    succ.left = None
                    total += node.val
                    node.val = total
                    node = node.left

        return root

Rust


Swift


Reference

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!