Java 求解如何把二叉搜索樹轉換為累加樹

Posted on by

一、題目

給出二叉搜索樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等於原樹中大於或等於 node.val 的值之和。

提醒一下，二叉搜索樹滿足下列約束條件：
節點的左子樹僅包含鍵 小於 節點鍵的節點。
節點的右子樹僅包含鍵 大於 節點鍵的節點。
左右子樹也必須是二叉搜索樹。

在這裡插入圖片描述

二、題解

觀察示例圖發現，樹的遍歷順序為右，中，左的順序，每個節點的值，是按照這個順序累加的狀態

在這裡插入圖片描述

由於是需要累加，所以需要pre指針記錄當前遍歷節點cur的前一個節點，方便累加

（1）確定遞歸函數及返回值

題目需要遍歷整棵樹，同時需要定義一個全局變量 pre，用來保存 cur節點的前一個節點的數值

（2）確定遞歸終止條件

遇到空就終止

（3）確定單層遞歸的邏輯

遍歷的順序，右，中，左

三、代碼

class Solution {
    // 記錄前驅節點
    int pre = 0;

    public TreeNode convertBST(TreeNode root) {
        // 空節點終止
        if (root == null) {
            return root;
        }
        // 遍歷順序：右，中，左
        convertBST(root.right);
        root.val += pre;
        pre = root.val;
        convertBST(root.left);
        return root;
    }
}

四、總結

觀察示例節點的規律，需要記錄上個節點的情況，註意引入前驅節點pre

到此這篇關於Java 求解如何把二叉搜索樹轉換為累加樹的文章就介紹到這瞭,更多相關Java 二叉搜索樹轉換為累加樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：