TK_blog

Description Construct Binary Tree from Preorder and Inorder Traversal https://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Construct Binary Tree from Inorder and Postorder Traversal https://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ Difficulty: 2.0/5.0 Solution Obviously we should recover the BST in a recursive manner. The pre/post-order traversal can be used to determine...

Description https://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Difficulty: 2.0/5.0 Solution class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int> > result; zigzag_helper(result, 1, root); for (int i = 1; i < result.size(); i+=2) reverse(result[i].begin(), result[i].end()); return result; } void zigzag_helper(vector<vector<int> >& result, int height,...

Description https://oj.leetcode.com/problems/path-sum-ii/ Difficulty: 1.5/5.0 Solution Note that the sum can be negative, which prevents us from pruning. class Solution { public: void pathSumHelper(vector<vector<int> > & result, vector<int>&path, TreeNode* pt, int remaining){ remaining -= pt->val; path.push_back(pt->val); if (!pt->left && !pt->right &&...

Description https://oj.leetcode.com/problems/linked-list-cycle/ https://oj.leetcode.com/problems/linked-list-cycle-ii/ Solution Solutions to both problems are based on slow-fast pointers. If there is a cycle, the the slow and fast pointer will meet finally. class Solution { public: bool hasCycle(ListNode *head) { ListNode * slowPt = head,...

Description https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ Difficulty: 3.5/5.0 Solution This is a very interesting problem. The key difficuly we are faced with is lack of random access to the elements. However, a list of ascending nodes can be viewed as a in-order traverval of...