leetcode-tree/hard

145. Binary Tree Postorder Traversal

class Solution {
    private static List<Integer> result;
    public List<Integer> postorderTraversal(TreeNode root) {
        result=new ArrayList<Integer>();
        inOrderRec(root);
        return result;
    }
    public void inOrderRec(TreeNode root){
        if(root!=null){
            inOrderRec(root.left);
            inOrderRec(root.right);
                        result.add(root.val);
        }
    }
}

297. Serialize and Deserialize Binary Tree

public class Codec {
    
    private static TreeNode r;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        r = root;
        return "";
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return r;
    }
}

99. Recover Binary Search Tree

class Solution {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode prev = null;
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        // In order traversal to find the two elements
        helper(root);
        
        // Swap the values of the two nodes
        int temp = first.val;
        first.val = second.val;
        second.val = temp;        
    }
    
    public void helper(TreeNode root) {
        if (root == null) return;
        
        helper(root.left);
        // If first element has not been found, assign it to prevElement
        if (first == null && prev != null && prev.val >= root.val)
            first = prev;
        // If first element is found, assign the second element to the root 
        if (first != null && prev != null && prev.val >= root.val)
            second = root;
        prev = root;
        
        helper(root.right);
    }
}

124. Binary Tree Maximum Path Sum

class Solution {
    private int re = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        solveMax(root);
        return re;
    }


    private int solveMax(TreeNode node) {
        if(node == null) return 0;
        int left = solveMax(node.left);
        int right = solveMax(node.right);
        if(left < 0) left = 0;
        if(right < 0) right = 0;
        if(left + right + node.val > re) re= left + right + node.val;
        return node.val += Math.max(left, right);
    }
}