Java中如何把二叉搜索樹轉(zhuǎn)換為累加樹

這篇文章主要介紹了Java中如何把二叉搜索樹轉(zhuǎn)換為累加樹，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

一、題目

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

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

二、題解

觀察示例圖發(fā)現(xiàn)，樹的遍歷順序為右，中，左的順序，每個節(jié)點的值，是按照這個順序累加的狀態(tài)

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

（1）確定遞歸函數(shù)及返回值

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

（2）確定遞歸終止條件

遇到空就終止

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

遍歷的順序，右，中，左

三、代碼

class Solution {
    // 記錄前驅(qū)節(jié)點
    int pre = 0;

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

感謝你能夠認真閱讀完這篇文章，希望小編分享的“Java中如何把二叉搜索樹轉(zhuǎn)換為累加樹”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業(yè)資訊頻道，更多相關知識等著你來學習!