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;
    }