By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

1.1、解题思路

只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树

1.2、算法

int sum = 0;
public TreeNode convertBST(TreeNode root) {
    if (root != null) {
        //找到最大的值
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        //开始走做节点了
        convertBST(root.left);
    }
    return root;
}

1.3、测试


@Test
public void test(){
    System.out.println(convertBST(initTreeNode()));
}

​

ContactAuthor