leetcode 538. 把二叉搜索树转换为累加树(二叉搜索树)

xiaoxiao2021-02-28  25

题目描述:

 

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

输入: 二叉搜索树: 5 / \ 2 13 输出: 转换为累加树: 18 / \ 20 13

思路一、看到题目第一个想法是中序遍历访问二叉树每个结点,得到有序序列并按顺序存储在数组中,接下来就只要再遍历一遍二叉树,并根据数组把相应的值加到各结点中就ok了。

思路二、用递归的方法:(自创)

        1.当前结点值要加的值有:父节点传递的值(即s,初始为0)、右孩子树所有结点的值(sum_value()函数来求).

      2.更新完当前结点的值后,如果左孩子存在,则通过递归调用左子树把当前结点更新后的值传给左孩子结点(root->left=f(root->left,root->val);)

        3.递归调用右子树,并把传给当前结点的值传递给右孩子(root->right=f(root->right,s);)

代码:

class Solution { public: TreeNode* convertBST(TreeNode* root) { int s=0; return f(root,s); } TreeNode* f(TreeNode* root,int s){ if(root==NULL)return NULL; int sum=0; sum_value(root->right,sum); root->val+=sum+s; if(root->left) root->left=f(root->left,root->val); root->right=f(root->right,s); return root; } void sum_value(TreeNode* root,int&sum){ if(root==NULL)return; sum+=root->val; sum_value(root->left,sum); sum_value(root->right,sum); } };
转载请注明原文地址: https://www.6miu.com/read-2599971.html

最新回复(0)