【3错-3】Convert BST to Greater Tre

https://leetcode.com/problems/convert-bst-to-greater-tree/

日期	是否一次通过	comment
2018-12-10 22:08	看答案	理解不透
2018-12-11 21:36	递归一次性通过，非递归靠答案debug	while(curNode.right != null) {curNode = curNode.right; nodeStack.push(curNode); } 括号中right写成left
2018-12-12 20:58	递归一次性通过，非递归写的很流畅，但是语法问题导致每一次性通过	坑在语法，和过分自信

image.png
（来源：https://leetcode.com/problems/convert-bst-to-greater-tree/）
类中序遍历，只要保留上一次的数值即可

递归

class Solution {
    public TreeNode convertBST(TreeNode root) {
        TreeNode prevNode = new TreeNode(0);
        dfs(root, prevNode);
        
        return root;
    }
    
    private void dfs(TreeNode root, TreeNode prevNode) {
        if(root == null) {
            return;
        }
        
        dfs(root.right, prevNode);
        root.val += prevNode.val;
        prevNode.val = root.val;
        dfs(root.left, prevNode);
        
    }
}

非递归

class Solution {
    public TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return root;
        }
        
        int midSum = 0;
        Stack<TreeNode> nodeStack = new Stack<>();
        TreeNode temp = root;  // 这行很关键，否则root会==null
        while(temp != null) {
            nodeStack.push(temp);
            temp = temp.right;
        }
        
        while(!nodeStack.isEmpty()) {
            TreeNode curNode = nodeStack.peek();
            curNode.val += midSum;
            midSum = curNode.val;
            
            if(curNode.left == null) {
                curNode = nodeStack.pop();
                while(!nodeStack.isEmpty() && nodeStack.peek().left == curNode) {
                    curNode = nodeStack.pop();
                }
            } else{
                curNode = curNode.left;
                while(curNode != null) {
                    nodeStack.push(curNode);
                    curNode = curNode.right;
                }
                
            }
        }
        
        return root;
    }
}