題目描述

給定一個二叉搜索樹（Binary Search Tree），把它轉(zhuǎn)換成為累加樹（Greater Tree)，使得每個節(jié)點的值是原來的節(jié)點值加上所有大于它的節(jié)點值之和。
538. 把二叉搜索樹轉(zhuǎn)換為累加樹

解法1 迭代

首先明確我們的目的：使得每個節(jié)點的值是原來的節(jié)點值加上所有大于它的節(jié)點值之和。
然后注意到輸入的樹是一棵二叉搜素樹，二叉搜索樹的每個節(jié)點值都大于它左邊的所有節(jié)點值，小于它右邊的所有節(jié)點值。
因此，我們可以從最右邊的節(jié)點開始，累加節(jié)點的值存放于sum，每移動到下一個節(jié)點，將sum再加上該節(jié)點的值并賦給它本身。這一思路要求我們的節(jié)點遍歷順序是從右往左走。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return root;
        }
        int sum = 0;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            //到達最右邊的節(jié)點
            while (curr != null) {
                stack.push(curr);
                curr = curr.right;
            }
            curr = stack.pop();
            //累加值到sum上
            sum += curr.val;
            //賦值給當前節(jié)點
            curr.val = sum;
            //下一個節(jié)點
            curr = curr.left;
        }
        return root;
    }
}

解法2 回溯

同樣的思路。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //num需要是全局遍歷，如果在convertBST函數(shù)體內(nèi)，遞歸回上一層num會改變。
    int num = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.right = convertBST(root.right);
        num += root.val;
        root.val = num;
        root.left = convertBST(root.left);
        return root;
    }
}