Tree Traversal (In-order / Level-order)

Last time we have talked about the pre-order traversal and post-order traversal of a binary tree (see here). Now let's look at another two traversals and how we can implement the traversal algorithm in C++. Let's first define the tree node here. For each node, we will have a value and two tree node pointers… Continue reading Tree Traversal (In-order / Level-order)

Tree Traversal (preorder / postorder)

Let’s continue… First, I want to cite a great explanation about tree traversal. There are generally two approaches related to tree traversal: BFS and DFS. Bread First Search (BFS): We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before… Continue reading Tree Traversal (preorder / postorder)

Word Break I && II

Let's continue... Problem Statement: Word Break I Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may… Continue reading Word Break I && II

Unique Path I && II (Recursion and Dynamic Programming)

Problem Statement: Unique Path I A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the… Continue reading Unique Path I && II (Recursion and Dynamic Programming)

Search in Rotated Sorted Array

Problem Statement: Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity… Continue reading Search in Rotated Sorted Array

Next Permutation and Longest Valid Parentheses

Let’s continue… Problem Statement: Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples. Inputs… Continue reading Next Permutation and Longest Valid Parentheses

Divide Two Integers and Sub String with Concatenation of All Words

Let’s continue… Problem Statement: Divide Two Integers Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero. Example 1: Input: dividend = 10, divisor = 3 Output: 3 Example 2: Input: dividend = 7,… Continue reading Divide Two Integers and Sub String with Concatenation of All Words

Swap Nodes in Pairs and Reverse Nodes in K Groups

Let’s continue… Problem Statement: Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. Example: Given 1->2->3->4, you should return the list as 2->1->4->3. Note: Your algorithm should use only constant extra space. You may not modify the values in the list's nodes, only nodes itself may be changed.… Continue reading Swap Nodes in Pairs and Reverse Nodes in K Groups

Remove Nth Node from End of List and Generate Parentheses

Let’s continue… Problem Statement: Remove Nth Node from End of List Given a linked list, remove the n-th node from the end of list and return its head. Example: Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always… Continue reading Remove Nth Node from End of List and Generate Parentheses