题目

leetcode:538
实话实说,这道题的意思是真没看懂,

代码与解析


从右面看会发现线索
可以采用右中左的顺序遍历,我采用了记录前一个节点的方式

func convertBST(root *TreeNode) *TreeNode {
    var pre *TreeNode
    var helper func (root *TreeNode)*TreeNode
    helper = func (root *TreeNode)*TreeNode{
        if root==nil{
            return root
        }
        helper(root.Right)
        if pre!=nil{
            root.Val += pre.Val
            // fmt.Println(pre.Val)
        }
        pre = root
        helper(root.Left)
        return root
    }
    return helper(root)
}

或者这样做

func convertBST(root *TreeNode) *TreeNode {
    if nil == root {
        return nil
    }
    convert(root, 0)
    return root
}

func convert(root *TreeNode, sum int) int {
    if root==nil {
        return sum
    }
    // 右面的子树用sum来接受
    sum = convert(root.Right, sum)
    sum += root.Val
    // 给当前节点赋值
    root.Val = sum
    sum = convert(root.Left, sum)
    return sum
}

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:191 个
  • 运行天数:1006 天
  • 访问总数:124265 人次

浙公网安备33011302000604

辽ICP备20003309号