Java教程

【LeetCode笔记】538. 把二叉搜索树转换为累加树(Java、二叉搜索树、递归)

本文主要是介绍【LeetCode笔记】538. 把二叉搜索树转换为累加树(Java、二叉搜索树、递归),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 题目描述
  • 思路 & 代码

题目描述

  • 注意是二叉搜索树,可以找出顺序
  • 有点类似中序遍历
    在这里插入图片描述

思路 & 代码

  • 思路:当前结点 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;
    }
}
这篇关于【LeetCode笔记】538. 把二叉搜索树转换为累加树(Java、二叉搜索树、递归)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!