一、題目

給出二叉搜索樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（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 二叉搜索樹轉換為累加樹內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

原文鏈接：https://blog.csdn.net/nanhuaibeian/article/details/121096863