Java Inverted InOrder


  • 0
    public int currSum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null) return null;
        invertedInOrder(root);
        return root;
    }
    public void invertedInOrder(TreeNode root) {
        if(root.right!=null) invertedInOrder(root.right);
        currSum+=root.val;
        root.val=currSum;
        if(root.left!=null) invertedInOrder(root.left);
    }
    

  • 0
    P

    Same idea, just recursive way.

     public TreeNode convertBST(TreeNode root) {
            if (root == null){
                return null;
            }
            Stack<TreeNode> stack = new Stack<>();
            int pre = 0;
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()){
                while (cur != null){
                    stack.push(cur);
                    cur = cur.right;
                }
                cur = stack.pop();
                pre = cur.val + pre;
                cur.val = pre;
                cur = cur.left;
            }
            return root;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.