Binary Tree Postorder/Inorder/Preoder Traversal (non-recursive) -- LeetCode 145, 94

[Question]

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

[Analysis]
The state of recursive calls can be simulated by stacks. The key is to find the branch (left or right) where the stack pop() happened. The preorder/inorder,/postorder functions are placed in differnt branch (in, left, right) respectively.

[Solution]
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (!root) return {};
        stack<TreeNode*> st;
        TreeNode* p=root;
        st.push(p);
        
        vector<int> res;
        while(!st.empty()) {
            if (st.top()==p && !p->left && !p->right) { 
                //-- leave node is reached and is at the top of stack.
                res.push_back(st.top()->val);     //--shared by all orders.
                st.pop();
                continue;
            }
            if (st.top()==p) {
                //res.push_back(st.top()->val);    // -- pre-order output here.
                p=p->left;
                if (p) st.push(p);
            }
            else if (st.top()->left==p) {
                res.push_back(st.top()->val);     // -- in-order output here
                p=st.top()->right;
                if (p) st.push(p);
            }
            else if (st.top()->right==p) {
                //res.push_back(st.top()->val);   //-- post-order output here
                p=st.top();
                st.pop();
            }
        }

        return res;
    }
};

Binary Tree Maximum Path Sum -- LeetCode

[Question]

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

[Analysis]
If the path can be only link (i.e. no both left and right nodes of one node allowed to be in the path), the problem is simple. Suppose path with max single-sided path ending at Node N (from bottom to up),
       SingleSidePathMax(N) = max (N.value,
                                                     N.value+ SingleSidePathMax(N.left),
                                                     N.value+ SingleSidePathMax(N.right) );

Going through all nodes in the tree, this will get the max sum of single-sided path.

To consider the path with a node N, whose both left and right are included in the path, it can calculated by,
      PathMax(N) = max ( SingleSidePathMax(N), N.value+SingleSidePathMax(N.left) + SingleSidePathMax(N.right) );

Therefore, apply post-order traversal in the Binary Tree, and calculate the single-sided path max and dual-sided path max of each node, the max path sum of all paths can be found.

[Solution]
class Solution {
public:
    int maxSinglePath(TreeNode *root, int& maxSum) {
        if (!root)  return 0;
       
        if (!root->left && !root->right) {
            maxSum = max( maxSum, root->val);
            return root->val;
        }
       
        int leftMax = maxSinglePath( root->left, maxSum);
        int rightMax= maxSinglePath( root->right, maxSum);
        int singleMax = max( max(leftMax, rightMax) + root->val, root->val);
        maxSum = max( max(maxSum, singleMax), leftMax+rightMax+root->val);
        return singleMax;
    }
   
    int maxPathSum(TreeNode *root) {
        int max = INT_MIN;
        maxSinglePath(root, max);
        return max;
    }

};

Binary Tree Maximum Path Sum

[Question]
Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

[Analysis]
Define "maximum path to a given node" (MPN) as, the maximum path starts from a node under and ends at the node. The MPN(node) = max (node.val, node.val+MPN(node.left), node.val+MPN(node.right)).

The maximum path (P) via node N and with the sub-tree rooted by N will be,
         P(N) = (MPN( N.left )>0)?MPN(N.left):0 + N.val + (MPN(N.right)>0)?MPN(N.right):0)

So using post-order traversal, we can get all P(N) and find the maximum P(N).
                 

[Solution]


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSumToNode(TreeNode *root, int& cur_max) {
        if (root==NULL) return 0;
        int leftMax = maxPathSumToNode(root->left, cur_max);
        int rightMax= maxPathSumToNode(root->right, cur_max);
     
        int maxPathToRoot = max( max(leftMax+root->val, rightMax+root->val), root->val );
        int maxPathViaRoot = ((leftMax>0)?leftMax:0)
                            + root->val
                            + ((rightMax>0)?rightMax:0);
     
        if (maxPathViaRoot > cur_max) {
            cur_max = maxPathViaRoot;
        }
        return maxPathToRoot;
    }
 
    int maxPathSum(TreeNode *root) {
        if (root==NULL) return 0;
        int max = root->val;
        maxPathSumToNode( root, max );
        return max;
    }
};