Problem
Solution
Initial thoughts
Python implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
class : def __init__(self): self._sum = 0 def convertBST(self, root): """ :type root: TreeNode :rtype: TreeNode """ if root is None: return root self.convertBST(root.right) self._sum += root.val root.val = self._sum self.convertBST(root.left) return root
|
Java implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
* Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class { private int sum = 0; public TreeNode convertBST(TreeNode root) { if(root == null){ return root; } convertBST(root.right); this.sum += root.val; root.val = this.sum; convertBST(root.left); return root; } }
|
Time complexity
O(n).
Space complexity
O(n).
Links
538. Convert BST to Greater Tree
(中文版) 算法笔记: 力扣#538 把二叉搜索树转换为累加树
近期评论