Skip to content

Latest commit

 

History

History
358 lines (282 loc) · 9.36 KB

0538.把二叉搜索树转换为累加树.md

File metadata and controls

358 lines (282 loc) · 9.36 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

538.把二叉搜索树转换为累加树

力扣题目链接

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。

示例 1:

538.把二叉搜索树转换为累加树

  • 输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
  • 输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

  • 输入:root = [0,null,1]
  • 输出:[1,null,1]

示例 3:

  • 输入:root = [1,0,2]
  • 输出:[3,3,2]

示例 4:

  • 输入:root = [3,2,4,1]
  • 输出:[7,9,4,10]

提示:

  • 树中的节点数介于 0 和 104 之间。
  • 每个节点的值介于 -104 和 104 之间。
  • 树中的所有值 互不相同 。
  • 给定的树为二叉搜索树。

思路

一看到累加树,相信很多小伙伴都会疑惑:如何累加?遇到一个节点,然后在遍历其他节点累加?怎么一想这么麻烦呢。

然后再发现这是一棵二叉搜索树,二叉搜索树啊,这是有序的啊。

那么有序的元素如果求累加呢?

其实这就是一棵树,大家可能看起来有点别扭,换一个角度来看,这就是一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13],是不是感觉这就简单了。

为什么变成数组就是感觉简单了呢?

因为数组大家都知道怎么遍历啊,从后向前,挨个累加就完事了,这换成了二叉搜索树,看起来就别扭了一些是不是。

那么知道如何遍历这个二叉树,也就迎刃而解了,从树中可以看出累加的顺序是右中左,所以我们需要反中序遍历这个二叉树,然后顺序累加就可以了

递归

遍历顺序如图所示:

538.把二叉搜索树转换为累加树

本题依然需要一个pre指针记录当前遍历节点cur的前一个节点,这样才方便做累加。

pre指针的使用技巧,我们在二叉树:搜索树的最小绝对差二叉树:我的众数是多少?都提到了,这是常用的操作手段。

  • 递归函数参数以及返回值

这里很明确了,不需要递归函数的返回值做什么操作了,要遍历整棵树。

同时需要定义一个全局变量pre,用来保存cur节点的前一个节点的数值,定义为int型就可以了。

代码如下:

int pre; // 记录前一个节点的数值
void traversal(TreeNode* cur)
  • 确定终止条件

遇空就终止。

if (cur == NULL) return;
  • 确定单层递归的逻辑

注意要右中左来遍历二叉树, 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。

代码如下:

traversal(cur->right);  // 右
cur->val += pre;        // 中
pre = cur->val;
traversal(cur->left);   // 左

递归法整体代码如下:

class Solution {
private:
    int pre; // 记录前一个节点的数值
    void traversal(TreeNode* cur) { // 右中左遍历
        if (cur == NULL) return;
        traversal(cur->right);
        cur->val += pre;
        pre = cur->val;
        traversal(cur->left);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

迭代法

迭代法其实就是中序模板题了,在二叉树:前中后序迭代法二叉树:前中后序统一方式迭代法可以选一种自己习惯的写法。

这里我给出其中的一种,代码如下:

class Solution {
private:
    int pre; // 记录前一个节点的数值
    void traversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->right;   //
            } else {
                cur = st.top();     //
                st.pop();
                cur->val += pre;
                pre = cur->val;
                cur = cur->left;    //
            }
        }
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        pre = 0;
        traversal(root);
        return root;
    }
};

总结

经历了前面各种二叉树增删改查的洗礼之后,这道题目应该比较简单了。

好了,二叉树已经接近尾声了,接下来就是要对二叉树来一个大总结了

其他语言版本

Java

class Solution {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        convertBST1(root);
        return root;
    }

    // 按右中左顺序遍历,累加即可
    public void convertBST1(TreeNode root) {
        if (root == null) {
            return;
        }
        convertBST1(root.right);
        sum += root.val;
        root.val = sum;
        convertBST1(root.left);
    }
}

Python

递归

# 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 __init__(self):
        self.pre = TreeNode()

    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        '''
        倒序累加替换:  
        [2, 5, 13] -> [[2]+[1]+[0], [2]+[1], [2]] -> [20, 18, 13]
        '''
        self.traversal(root)
        return root

    def traversal(self, root: TreeNode) -> None:
        # 因为要遍历整棵树,所以递归函数不需要返回值
        # Base Case
        if not root: 
            return None
        # 单层递归逻辑:中序遍历的反译 - 右中左
        self.traversal(root.right)  # 右

        # 中节点:用当前root的值加上pre的值
        root.val += self.pre.val    # 中
        self.pre = root             

        self.traversal(root.left)   # 左

Go

弄一个sum暂存其和值

 //右中左
func bstToGst(root *TreeNode) *TreeNode {
     var sum int
     RightMLeft(root,&sum)
     return root
}
func RightMLeft(root *TreeNode,sum *int) *TreeNode {
    if root==nil{return nil}//终止条件,遇到空节点就返回
    RightMLeft(root.Right,sum)//先遍历右边
    temp:=*sum//暂存总和值
    *sum+=root.Val//将总和值变更
    root.Val+=temp//更新节点值
    RightMLeft(root.Left,sum)//遍历左节点
    return root
}

JavaScript

递归

var convertBST = function(root) {
    let pre = 0;
    const ReverseInOrder = (cur) => {
        if(cur) {
            ReverseInOrder(cur.right);
            cur.val += pre;
            pre = cur.val;
            ReverseInOrder(cur.left);
        }
    }
    ReverseInOrder(root);
    return root;
};

迭代

var convertBST = function (root) {
    let pre = 0;
    let cur = root;
    let stack = [];
    while (cur !== null || stack.length !== 0) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.right;
        }
        cur = stack.pop();
        cur.val += pre;
        pre = cur.val;
        cur = cur.left;
    }
    return root;
};

##C

递归

int pre;
void traversal(struct TreeNode* node) {
    if(!node)
        return ;
    traversal(node->right);
    node->val = node->val + pre;
    pre = node->val;
    traversal(node->left);
}

struct TreeNode* convertBST(struct TreeNode* root){
    pre = 0;
    traversal(root);
    return root;
}

TypeScript

递归法

function convertBST(root: TreeNode | null): TreeNode | null {
    let pre: number = 0;
    function recur(root: TreeNode | null): void {
        if (root === null) return;
        recur(root.right);
        root.val += pre;
        pre = root.val;
        recur(root.left);
    }
    recur(root);
    return root;
};

迭代法

function convertBST(root: TreeNode | null): TreeNode | null {
    const helperStack: TreeNode[] = [];
    let curNode: TreeNode | null = root;
    let pre: number = 0;
    while (curNode !== null || helperStack.length > 0) {
        while (curNode !== null) {
            helperStack.push(curNode);
            curNode = curNode.right;
        }
        curNode = helperStack.pop()!;
        curNode.val += pre;
        pre = curNode.val;
        curNode = curNode.left;
    }
    return root;
};