leetcode题解538-把二叉搜索树转化为累加树

问题描述

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

解题思路

要找到比某个结点值都大的所有结点，我们就应该想到有序性，这样每次找到一个结点，我们就让它加上后面所有结点的值即可。因为是**二叉搜索树，中序遍历结果有序，而我们想要得到的应该是逆中序序列，所以我们应该选择先遍历右子树，再遍历左子树。**另外，由于我们事先不知道结点的个数，所以我们应该用集合来存储累加后结点的值，因为是从值最大的结点一直处理到值最小的结点，依次得到其处理的结果，所以每次计算一个结点的累加值，就该结点的值直接加上上一个结点的累加值即可。

代码实现

public List<Integer> list;
	public void MidSearch(TreeNode p){
		//如果是空节点，就直接退出
        if(p==null){
            return;
        }
        //先遍历右孩子结点
		if(p.right!=null){
			MidSearch(p.right);
		}
		//如果“根”节点不为空，就处理累加
		if(p!=null){
			//如果这个结点不是第一个访问的结点，它的累加值就等于它本身的值加上上一个结点的累加值
            if(list.size()!=0){
                p.val=p.val+list.get(list.size()-1);
            }
            //把累加的结果放入到集合中
            list.add(p.val);
		}
		//再遍历左孩子结点
		if(p.left!=null){
			MidSearch(p.left);
		}
	}
	public TreeNode convertBST(TreeNode root) {
        list=new ArrayList<>();
		MidSearch(root);
		return root;
    }