文章目錄

• 題目描述
• 思路 & 代碼
• • • 更新版

題目描述

• 注意是二叉搜索樹，可以找出順序！
• 有點類似中序遍歷
  

思路 & 代碼

• 思路：當前結(jié)點 root 帶著父值一直走到最右邊，再一個個累加右值
• 更新 root.val += rightSum，然后以 root.val 作為左子樹的父值，遞歸這個過程
• 左子樹遞歸結(jié)束，當前 root 的棧幀返回左子樹的值（畢竟這邊才是最大值嘛）
• 時間復(fù)雜度O(n)，相當于遍歷每一個結(jié)點

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/ class Solution {public TreeNode convertBST(TreeNode root) {toConvertBST(root, 0);return root;}// 返回給父結(jié)點的賦值（當前已更新子樹最左值）int toConvertBST(TreeNode root, int paNum){// 往右走，一直走到結(jié)束,返回父值if(root == null){return paNum;}// 先把父值傳到最右邊int rightSum = toConvertBST(root.right, paNum);// 當前值等于 當前 + 右子樹的最左值root.val += rightSum; // 把當前和當作父值，傳給左結(jié)點int leftSum = toConvertBST(root.left, root.val);// 返回左值return leftSum;} }

更新版

• 一段時間過去后，寫出了更加簡單的代碼呢！
• 思路還是：右 - 根 - 左，遞歸

class Solution {int preNum = 0;public TreeNode convertBST(TreeNode root) {if(root != null) {convertBST(root.right);root.val += preNum;preNum = root.val;convertBST(root.left);}return root;} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】538. 把二叉搜索树转换为累加树（Java、二叉搜索树、递归）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。