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

一、題目

給出二叉搜索樹的根節點,該樹的節點值各不相同,請你將其轉換為累加樹(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!

推薦閱讀: