一区二区免费在线观看,中文字幕精品一区二区三区精品,99这里只有精品

一、題目

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

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

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

二、題解

觀察示例圖發(fā)現(xiàn)，樹的遍歷順序?yàn)橛遥校蟮捻樞颍總€(gè)節(jié)點(diǎn)的值，是按照這個(gè)順序累加的狀態(tài)

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

由于是需要累加，所以需要pre指針記錄當(dāng)前遍歷節(jié)點(diǎn)cur的前一個(gè)節(jié)點(diǎn)，方便累加

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

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

（2）確定遞歸終止條件

遇到空就終止

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

遍歷的順序，右，中，左

三、代碼

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

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