Minimal path sum from root to leaves | Coding Melon
Given a tree, return the minimal path sum from the root to the leaves.
Read full article from 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;}