文章目录

• 题目描述
• 思路 & 代码

题目描述

• 注意是二叉搜索树，可以找出顺序！
• 有点类似中序遍历
  

思路 & 代码

• 思路：当前结点 root 带着父值一直走到最右边，再一个个累加右值
• 更新 root.val += rightSum，然后以 root.val 作为左子树的父值，递归这个过程
• 左子树递归结束，当前 root 的栈帧返回左子树的值（毕竟这边才是最大值嘛）
• 时间复杂度O(n)，相当于遍历每一个结点

/**
 * 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;
    }
    // 返回给父结点的赋值（当前已更新子树最左值）
    int toConvertBST(TreeNode root, int paNum){
        // 往右走，一直走到结束,返回父值
        if(root == null){
            return paNum;
        }
        // 先把父值传到最右边
        int rightSum = toConvertBST(root.right, paNum);
        // 当前值等于 当前 + 右子树的最左值
        root.val += rightSum; 
        // 把当前和当作父值，传给左结点
        int leftSum = toConvertBST(root.left, root.val);

        // 返回左值
        return leftSum;
    }
}