## Tuesday, January 5, 2016

### Minimal path sum from root to leaves | Coding Melon

Minimal path sum from root to leaves | Coding Melon
Given a tree, return the minimal path sum from the root to the leaves.
`int` `pathSum(TreeNode* root) {`
`    ``if` `(!root) {`
`        ``return` `0;`
`    ``}`
`    ``int` `leftSum = pathSum(root->left);`
`    ``int` `rightSum = pathSUm(root->right);`
`    ``return` `min(leftSum, rightSum) + root->val;`
`}`

more efficient one. using iterative method rather than recursive method.
`int` `pathSum(TreeNode* root) {`
`    ``if` `(!root){`
`        ``return` `0;`
`    ``}`
`    ``stack<TreeNode*> st;`
`    ``stack<``int``> stVal;`
`    ``minS = INT_MAX;`
`    ``st.push_back(root);`
`    ``stVal.push_back(root->val); `
`    ``while``(!st.empty()) {`
`        ``TreeNode* top = st.top();`
`        ``int` `val = stVal.top();`
`        ``st.pop();`
`        ``stVal.pop();`
`        ``if` `(top->left == NULL && top->right == NULL) {`
`            ``minS = min(minS, val);`
`        ``}`
`        ``if` `(top->right) {`
`            ``st.push_back(top->right);`
`            ``stVal.push_back(val + top->right->val);`
`        ``}`
`        ``if` `(top->left) {`
`            ``st.push_back(top->left);`
`            ``stVal.push_back(val + top->left->val);`
`        ``}`
`    ``}`
`    ``return` `minS;`
`}`

If the value of each tree node is non-negative.
`int` `pathSum(TreeNode* root) {`
`    ``if` `(!root){`
`        ``return` `0;`
`    ``}`
`    ``stack<TreeNode*> st;`
`    ``stack<``int``> stVal;`
`    ``minS = INT_MAX;`
`    ``st.push_back(root);`
`    ``stVal.push_back(root->val); `
`    ``while``(!st.empty()) {`
`        ``TreeNode* top = st.top();`
`        ``int` `val = stVal.top();`
`        ``st.pop();`
`        ``stVal.pop();`
`        ``if` `(top->left == NULL && top->right == NULL) {`
`            ``minS = min(minS, val);`
`        ``}`
`        ``if` `(top->right && val + top->right->val < minS) {`
`            ``st.push_back(top->right);`
`            ``stVal.push_back(val + top->right->val);`
`        ``}`
`        ``if` `(top->left && val + top->left->val < minS) {`
`            ``st.push_back(top->left);`
`            ``stVal.push_back(val + top->left->val);`
`        ``}`
`    ``}`
`    ``return` `minS;`
`}`