Tree Hard Problem

Algorithm

1. Path Sum Maximum

For each node like following, there should be four ways existing for max path:

• 1. Node only （因为本题中的节点可能是负值！）
• 1. L-sub + Node
• 1. R-sub + Node
• 1. L-sub + Node + R-sub

Idea:

• arch代表穿过当前节点的路径（左边一支儿+自己节点+右边一支儿）。
• 注意树的节点可以是负数，所以arch不一定是最长的。
• 每次return以root（当前节点）开头最大的单只path sum。
• res[]就是一个存result的reference object，java不支持c++那种直接&传reference，
• 所以要么用个长度为一的数组，要么写个wrapper。还是用数组简单。
• update res[0]，用arch和以自己开头一支儿的比，谁大就把res[0] update成谁。

class solution{
    int maxVal;
    public int maxPathSum(TreeNode root) {
        maxVal = Integer.MIN_VALUE;
        helper(root, maxVal);
        return maxVal;
    }
    private int helper(TreeNode node , int maxVal) {
        if(node==null)
            return 0;
        int left = helper(node.left, maxVal);
        int right = helper(node.right, maxVal);
        int passArch = left + right + node.val;
        int nopass = Math.max(node.val, Math.max(right, left)+node.val);
        maxVal =Math.max(maxVal, Math.max(passArch, nopass));
        return nopass;
    }
}

2. Recover Tree

Key Point:

• Preorder reverse elements detect;
• Global field: node1, node2 , and pre-node (variable for reference)

If we change the value 4 and 8: 1 3 8 6 7 4 10 13 14, when it goes to the node 6, now the pre->val = 8, check if pre6). So we store the first pointer pointing to the node 6 and second pointer pointing to the node 8. To do so, we have stored the wrong nodes, if every other node keep the correct order, then swapping these nodes is enough for the problem. In other words, after the whole traversal, what we need to do is just changing the values of the first and second. Continue our example here, when the traversal goes to the node 4, now the node 7 is its pre, which is also wrong, so the second wrong node is found, and we change the second pointer pointing to node 4.

 class RecoverTree {
    TreeNode node1 = null, node2 = null, prePtr = null;
    // prePtr is the current pre-node on preorder
    // node1, node2 are the two nodes need to be swap
    public void recoverTree(TreeNode root) {
        if (root == null)
            return;
        dfsFinder(root);
        swap(node1, node2);
    }
    // preorder traversal
    private void dfsFinder(TreeNode node) {
        if (node == null)
            return;
        if (node.left != null)
            dfsFinder(node.left);
        if (prePtr != null && prePtr.val > node.val) {
            if (node1 == null)
                node1 = prePtr; // first node in first time reverse order
                                // detected
            node2 = node; // second node in reverse order for second time
                            // detected
        }
        prePtr = node; // update all the time for prePointer
        dfsFinder(node.right);
    }
    private void swap(TreeNode node1, TreeNode node2) {
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
}

3. Populating Next Right Pointers in Each Node II

class PopulatingNextRightPointersII {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode lastHead = root; // last level head node(the parent of
                                        // current node)
        TreeLinkNode pre = null; // current previous pointer
        TreeLinkNode curHead = null; // current level head node
        while (lastHead != null) {
            TreeLinkNode lastCur = lastHead;
            while (lastCur != null) { 
                // in this while loop, nodes are made up in the same line
                // each time to make sure the curhead is null or not null
                // assign curHead once current node has child
                if (lastCur.left != null) {
                    if (curHead == null) {
                        curHead = lastCur.left;
                        pre = curHead;
                    } else {
                        pre.next = lastCur.left;
                        pre = pre.next;
                    }
                }               
                if (lastCur.right != null) {
                    if (curHead == null) {
                        /**
                         *  for situation: 
                         *            O (lastCur)   --->       O
                         *         /      \                 /      \
                         *    null        O(nextHead)     O         O
                         */
                        curHead = lastCur.right;
                        pre = curHead;
                    } else {
                        // this is normal case;
                        pre.next = lastCur.right;
                        pre = pre.next;
                    }
                }
                lastCur = lastCur.next; // change to next parent
            }
            //  do next line
            lastHead = curHead;
            curHead=null;
        }
    }
}