563. Binary Tree Tilt

https://leetcode.com/problems/binary-tree-tilt/description/
Solution 1. Recursive post order traversal.
    void tilt(TreeNode *node, int &s, int &st) {
        if(!node) return;
        int sl=0, sr=0;
        tilt(node->left, sl, st);
        tilt(node->right, sr, st);
        s = node->val + sl + sr;
        st += abs(sl-sr);
    }
    int findTilt(TreeNode* root) {
        int s = 0, st = 0;
        tilt(root, s, st);
        return st;
    }
or
    int tilt(TreeNode *node, int &st) {
        if(!node) return 0;
        int sl = tilt(node->left, st);
        int sr = tilt(node->right, st);
        st += abs(sl-sr);
        return node->val + sl + sr;
    }
    int findTilt(TreeNode* root) {
        int st = 0;
        tilt(root, st);
        return st;
    }
Solution 2. Iterative post order traversal. Using maps to save the sums and tilts of the sub-tree at a particular node. (much slow by using the maps)


    int findTilt(TreeNode* root) {
        if(!root) return 0;
        int tilt = 0, sumL = 0, sumR = 0, sumA = 0;
        TreeNode* node = root;
        TreeNode* last, *top;
        stack<TreeNode*> st;
        unordered_map<TreeNode*, int> ms;
        unordered_map<TreeNode*, int> mt;
        ms[nullptr] = 0;
        mt[nullptr] = 0;
        while(!st.empty() || node) {
            if(node) {
                st.push(node);
                node = node->left;
            }
            else {
                top = st.top();
                if(top->right && last != top->right) {
                    node = top->right;
                }
                else {
                    ms[top] += top->val + ms[top->left] + ms[top->right];
                    mt[top] += abs(ms[top->left] - ms[top->right]) + (mt[top->left] + mt[top->right]);
                    last = top;
                    st.pop();
                }
            }
        }
        
        return mt[root];

    }