[LeetCode] 1162. As Far from Land as Possible

 Problem : https://leetcode.com/problems/as-far-from-land-as-possible/description/

Start from all the land cells and use BFS approach to calculate Manhattan distance for each water cells.

Manhattan distance means on each step, we can move to the 4 conjunctive cells ( up, down, left, right ).

Because of memorization, each cell will only be visited once.

Time complexity : O ( M * N ), M = len(grid), N = len(grid[0])

class Solution {
    static final int[][] diffs = new int[][] { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

    public int maxDistance(int[][] grid) {
        int ROW = grid.length;
        int COLUMN = grid[0].length;

        int[][] memo = new int[ROW][COLUMN];
        Deque<int[]> queue = new LinkedList<>();

        for (int y = 0; y < ROW; y++) {
            for (int x = 0; x < COLUMN; x++) {
                if (grid[y][x] == 1)
                     queue.offerLast(new int[] {y, x});
            }
        }

        int result = -1;
        int step = 1;
        
        while (!queue.isEmpty()) {
            int n = queue.size();

            for (int i = 0; i < n; i++) {
                int[] cur = queue.pollFirst();
                int cy = cur[0], cx = cur[1];

                for (int[] d : diffs) {
                    int ny = cy + d[0], nx = cx + d[1];

                    if (0 <= ny && ny < ROW && 
                        0 <= nx && nx < COLUMN && 
                        grid[ny][nx] == 0 && 
                        (memo[ny][nx] == 0 || memo[ny][nx] > step)) {
                        memo[ny][nx] = step;
                        queue.offerLast(new int[] {ny, nx});
                    }
                }
            }

            if (!queue.isEmpty()) {
                result = Math.max(result, step);
            }
            
            step += 1;
        }


        return result;
    }
}

[LeetCode] 909. Snakes and Ladders

Problem : https://leetcode.com/problems/snakes-and-ladders/description/

This problem can be solved with BFS algorithm.

Each square on the board might be visited by regular visit or by using a ladder.   So each square has 2 visited states. Start from the index 1 square and use BFS algorithm to find the least steps to reach to the N*N square.

class Solution {
    public int snakesAndLadders(int[][] board) {
        int N = board.length;

        // Every square may be visited by a regular movement or by using a ladder
        boolean[][] visited = new boolean[N*N+1][2];

        Deque<Integer> queue = new LinkedList<>();
        queue.offerLast(1);
        visited[1][0] = true;

        int result = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                int currentIndex = queue.pollFirst();

                // reach the destination 
                if (currentIndex == N*N) {
                    return result;
                }
                
                for (int j = 1; j <= 6 && currentIndex + j <= N * N; j++) {
                    int nextIndex = currentIndex + j;
                    int[] nextPos = indexToPos(nextIndex, N);

                    if (board[nextPos[0]][nextPos[1]] != -1) {
                        // if the square has ladder
                        int jumpIndex = board[nextPos[0]][nextPos[1]];
                        
                        // check if this square has been visited by using ladder
                        if (visited[jumpIndex][1]) {
                            continue;
                        }

                        visited[jumpIndex][1] = true;
                        queue.offerLast(jumpIndex);
                    } else {
                        // if this square has been visited by regular movement
                        if (visited[nextIndex][0]) {
                            continue;
                        }
                        visited[nextIndex][0] = true;
                        queue.offerLast(nextIndex);
                    }

                }
            }

            result += 1;
        }

        return -1;
    }

    int[] indexToPos(int i, int N) {
        // find the row index
        int y = (N - 1)  - (i-1) / N;

        // find the column index
        int x = (i-1) % N;

        // revert the column order on the row "y" if it is needed
        if (y % 2 == N % 2) {
            x = (N-1) - x;
        }

        return new int[] { y, x };
    }
}

[LeetCode] 1345. Jump Game IV

 Problem : https://leetcode.com/problems/jump-game-iv/

Covert the array to a graph. Then use BFS find the shortest path.

class Solution {
    public int minJumps(int[] arr) {
        int N = arr.length;
        boolean[] visited = new boolean[N];
        
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < N; i++) {
            List<Integer> tmp = graph.getOrDefault(arr[i], new ArrayList<Integer>());
            tmp.add(i);
            graph.put(arr[i], tmp);
        }
        
        int step = 0;
        visited[0] = true;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curPos = queue.poll();
                if (curPos == N-1) {
                    return step;
                }
                
                if (curPos - 1 >= 0 && !visited[curPos - 1]) {
                    visited[curPos - 1] = true;
                    queue.offer(curPos - 1);
                }
                
                if (curPos + 1 < N && !visited[curPos + 1]) {
                    visited[curPos + 1] = true;
                    queue.offer(curPos + 1);
                }
                
                for (int nextPos : graph.get(arr[curPos])) {
                    if (nextPos != curPos && !visited[nextPos]) {  
                        visited[nextPos] = true;
                        queue.offer(nextPos);
                    }
                }
                
                // important! 
                // clear the neighbore pos list to avoid redundant visiting.
                graph.get(arr[curPos]).clear(); 
            }
            
            step += 1;
        }
        
        return step;
    }
}

[LeetCode] 1306. Jump Game III

Problem : https://leetcode.com/problems/jump-game-iii/

A typical BFS problem. In case it encounters a loop during the traversal, it is impossible to reach to the position with value 0.

Time complexity = O ( N ).   N = length of the arr. Because we need to every item in the input array at least once.

class Solution {
    public boolean canReach(int[] arr, int start) {
        if (arr[start] == 0) return true;
        
        int N = arr.length;
        boolean[] visited = new boolean[N];
        visited[start] = true;
        
        Queue<Integer> queue = new LinkedList();
        queue.offer(start);
        
        int[] diffs = new int[] {1, -1};
        
        while (!queue.isEmpty()) {
            int index = queue.poll();
                        
            for (int d : diffs) {
                int next  = index + d * arr[index];
                if (next >= 0 && next < N && !visited[next]) {
                    if (arr[next] == 0) return true;

                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        
        return false;
    }
}

[LeetCode] 429. N-ary Tree Level Order Traversal

 Problem : https://leetcode.com/problems/n-ary-tree-level-order-traversal/

BFS Solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        
        queue = [root]
        result = []
        
        while queue:
            result.append([node.val for node in queue])
            queue = [child for node in queue for child in node.children]
        
        return result

DFS Solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root: return []
        
        result = []
        
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
            
            for child in reversed(node.children):
                stack.append((child, level+1))
        
        return result

[LeetCode] 863. All Nodes Distance K in Binary Tree

 Problem : https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

It is straightforward  to use BFS to collect the nodes on distance K in the binary tree. 

To support move upward and downward simultaneously, we need to add one more pointer to point from each node to its parent node. So we convert the given binary tree to a directed graph. 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        
        # use dfs to find parent of each nodes
        parent = {root: None}
        def dfs(node):
            for child in [node.left, node.right]:
                if child:
                    parent[child] = node
                    dfs(child)
        
        dfs(root)
        
        # start from target node and use bfs to find all nodes on distance k
        queue = deque([target])
        visited = set([target])
        
        result = []
        step = 0
        
        while queue and step <= k:
            for _ in range(len(queue)):
                node = queue.popleft()
                if step == k:
                    result.append(node.val)
                
                for nxt in [node.left, node.right, parent[node]]:
                    if nxt and nxt not in visited:
                        visited.add(nxt)
                        queue.append(nxt)
                
            step += 1
                
        return result

[LeetCode] 542. 01 Matrix

 Problem : https://leetcode.com/problems/01-matrix/

Start from all '0' cells and use BFS to find the shortest distance to '1' cells.

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        ROW = len(mat)
        COLUMN = len(mat[0])
        
        result = [[ROW*COLUMN] * COLUMN for _ in range(ROW)]
        queue = deque([])
        
        for y in range(ROW):
            for x in range(COLUMN):
                if mat[y][x] == 0:
                    result[y][x] = 0
                    queue.append((y, x))
        
        step = 1
        
        while queue:
            for _ in range(len(queue)):
                y, x= queue.popleft()

                for dy, dx in [(0,1), (0,-1), (1,0), (-1,0)]:
                    ny = y + dy
                    nx = x + dx
                    if 0 <= ny < ROW and 0 <= nx < COLUMN:
                        if step > result[ny][nx]:
                            continue

                        result[ny][nx] = step
                        queue.append((ny, nx))
            
            step += 1
            
        return result

[LeetCode] 310. Minimum Height Trees

 Problem : https://leetcode.com/problems/minimum-height-trees/

The entire process is like peeling an onion.  Keep removing vectors only has 1 edge until the graph has less than 2 vectors left. Return the remaining vectors as the root of MHTs.

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {   
        int[] degree = new int[n];
        Map<Integer, List<Integer>> graph = new HashMap();
        
        // construct the graph
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            
            if (!graph.containsKey(a)) {
                graph.put(a, new ArrayList<Integer>());
            }
            
            if (!graph.containsKey(b)) {
                graph.put(b, new ArrayList<Integer>());
            }
            
            graph.get(a).add(b);
            graph.get(b).add(a);
            
            degree[a] += 1;
            degree[b] += 1;
        }
        
        // start to peel the onion
        Queue<Integer> queue = new LinkedList();
        boolean[] deleted = new boolean[n];
        int remains = n;
        
        for (int i = 0; i < n; i++) {
            // put all nodes on outline to the queue
            if (degree[i] <= 1) {
                queue.offer(i);
            }
        }
        
        // peel the onion until less than 2 nodes are left
        // a MHT can have 2 possible roots in maximum
        while (remains > 2) {
            int size = queue.size();
            // use for-loop to ensure peel all nodes on current layer
            for (int i = 0; i < size; i++) {
                // peel the node off the tree
                int a = queue.poll();
                deleted[a] = true;
                degree[a] -= 1;
                remains -= 1;

                for (int b : graph.get(a)) {
                    if (deleted[b]) {
                        continue;
                    }

                    // put its peer to queue if the peer node is on the next layer
                    degree[b] -= 1;
                    if (degree[b] == 1) {
                        queue.offer(b);
                    }
                }
            }
        }
        
        // nodes on the last layer are MHT's root 
        return new ArrayList<Integer>(queue);
    }
}

Edited on 12/16/2021. Replace with Java solution.

[LeetCode] 297. Serialize and Deserialize Binary Tree

 Problem : https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Use BFS to serialize and deserialize the tree.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        output = []
        
        queue = deque([root])
        
        while queue:
            tmp = deque()
            
            while queue:
                node = queue.popleft()
                if not node:
                    output.append('#')
                else:
                    output.append(str(node.val))
                    tmp.append(node.left)
                    tmp.append(node.right)
                    
            queue = tmp
        
        return ','.join(output) if output[0] != '#' else ''
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        
        if not data:
            return None
        
        data = data.split(',')
        
        root = TreeNode(int(data[0]))
        i = 1
        
        queue = deque([root])
        
        while i < len(data):
            tmp = deque()
            
            while queue:
                node = queue.popleft()
                
                if data[i] == '#':
                    node.left = None
                else:
                    node.left = TreeNode(int(data[i]))
                    tmp.append(node.left)
                
                i += 1
                
                if data[i] == '#':
                    node.right = None
                else:
                    node.right = TreeNode(int(data[i]))
                    tmp.append(node.right)
                
                i += 1
            
            queue = tmp
        
        return root
                    
        
        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

[LeetCode] 257. Binary Tree Paths

Problem : https://leetcode.com/problems/binary-tree-paths/

DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        
        def dfs(node):
            if node:
                suffix = []
                
                if node.left:
                    suffix += dfs(node.left)
                    
                if node.right:
                    suffix += dfs(node.right)
                
                return [[str(node.val)] + s for s in suffix] if suffix else [[str(node.val)]]
                
        
        return ['->'.join(path) for path in dfs(root)]

Iterative DFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        # dfs
        stack = [(root, [root.val])]
        result = []
        
        while stack:
            node, path = stack.pop()
            
            if not node.left and not node.right:
                result.append('->'.join(map(str, path)))
            else:
                if node.right:
                    stack.append((node.right, path + [node.right.val]))
            
                if node.left:
                    stack.append((node.left, path + [node.left.val]))
                
        return result

BFS approach

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        queue = deque([[root]]) if root else deque()
        result = []
        
        while queue:
            path = queue.popleft()
            
            if path[-1].left:
                queue.append(path + [path[-1].left])
            if path[-1].right:
                queue.append(path + [path[-1].right])
            
            if not path[-1].left and not path[-1].right:
                result.append(path)
        
        return map(lambda p: '->'.join(p), map(lambda path: map(lambda n: str(n.val), path), result))

Edited on 04/22/2021. Refactor DFS solution by appending suffix collected from lower level.

Edited on 06/06/2021. Add iterative DFS solution.

[LeetCode] 222. Count Complete Tree Nodes

 Problem : https://leetcode.com/problems/count-complete-tree-nodes/

DFS Solution:

Time Complexity = O ( N )

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
        

BFS Solution:

Time Complexity = O ( N )

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        
        level = 0
        result = 0
        
        while queue:
            tmp = deque()
            result += len(queue)
            while queue:
                node = queue.popleft()
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            
            # stop traversal when reach the last level  
            if len(tmp) < 2 ** level:
                return result + len(tmp)
            
            queue = tmp
        return result

[LeetCode] 199. Binary Tree Right Side View

 Problem : https://leetcode.com/problems/binary-tree-right-side-view/

Use BFS to traverse the tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root : return []
        
        result = []
        
        queue = deque([root])
        while queue:
            N = len(queue)
            for i in range(N):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                    
                if node.right:
                    queue.append(node.right)
                
                # append the right-most node value
                if i == N-1:
                    result.append(node.val)
                    
        return result

DFS Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        
        if not root: return []
        
        result = []
        
        # dfs
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append(node.val)
            
            if node.left:
                stack.append((node.left, level+1))
                
            if node.right:
                stack.append((node.right, level+1))
                    
        return result

Edited on 05/31/2021. Add DFS solution.

[LeetCode] 139. Word Break

Problem : https://leetcode.com/problems/word-break/

Iterate the input string from left to right. Find word in dictionary. If found, break the input string into 2 parts, check if the 2nd part is also constructed by the words in dictionary.

Time Complexity = O ( N )

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        @lru_cache(maxsize=None)
        def dfs(start):
            if start >= len(s): 
                return True
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet and dfs(i+1):
                    return True
                    
            return False
        
        return dfs(0)

BFS solution:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        queue = deque([0])
        visited = set([0])
        
        while queue:
            start = queue.popleft()
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet:
                    if i + 1 == len(s):
                        return True

                    if i + 1 not in visited:
                        visited.add(i+1)
                        queue.append(i+1)
        
        return False

The bottom-up solution:

class Solution {

    public boolean wordBreak(String s, List wordDict) {
        HashSet<String> words = new HashSet();
        int wordLen = 0;
            
        for (int i = 0; i < wordDict.size(); i++) {
            words.add(wordDict.get(i));
            wordLen = Math.max(wordLen, wordDict.get(i).length());
        }
        
        int N = s.length();
        boolean[] dp = new boolean[N];
        
        for (int i = N-1; i >= 0; i--) {
            for (int j = i; i - j + 1 <= wordLen && j >= 0; j--) {
                
                if (words.contains(s.substring(j, i+1)) && (i + 1 == N || dp[i+1]) ) {
                    dp[j] = true;
                }
            }
        }
        
        return dp[0];

    }
}

Edited on 11/26/2021. Add the bottom-up solution.

[LeetCode] 127. Word Ladder

Problem : https://leetcode.com/problems/word-ladder/

Consider every word in wordList is a node of a graph. Use BFS to find the shortest path from begin word to end word.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        INT_MAX = 2 ** 31 - 1
        N = len(beginWord)
        
        wordDict = {word: INT_MAX for word in wordList}
        intermediates = defaultdict(list)
        
        if endWord not in wordDict: return 0
        
        for word in wordList:
            for i in range(N):
                wordMask = word[:i] + '*' + word[i+1:]
                intermediates[wordMask].append(word)
        
        queue = deque([beginWord])
        step = 1
        
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                
                for i in range(N):
                    wordMask = word[:i] + '*' + word[i+1:]

                    for newWord in intermediates[wordMask]:
                        if newWord == endWord:
                            return step + 1
                        
                        if newWord == word or wordDict[newWord] < step + 1:
                            continue
                        
                        wordDict[newWord] = step + 1
                        queue.append(newWord)

            step += 1
        
        return 0

Bidirectional BFS

Time complexity = O ( N * W * N + N * W * N ) = O ( W * N ** 2), N = length of each word, W = total number of word.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        INT_MAX = 2 ** 31 - 1
        N = len(beginWord)
        
        wordDict = {word: INT_MAX for word in wordList}
        intermediates = defaultdict(list)
        
        if endWord not in wordDict: return 0
        
        for word in wordList:
            for i in range(N):
                wordMask = word[:i] + '*' + word[i+1:]
                intermediates[wordMask].append(word)
        
        queue = set([beginWord])
        opposite = set([endWord])
        
        step = 1
        
        while queue:
            tmp = []
            
            for word in queue:
                for i in range(N):
                    wordMask = word[:i] + '*' + word[i+1:]

                    for newWord in intermediates[wordMask]:
                        if newWord in opposite:
                            return step + 1
                        
                        if newWord == word or wordDict[newWord] < step + 1:
                            # word has been visited
                            continue
                        
                        wordDict[newWord] = step + 1
                        tmp.append(newWord)
                        
            queue = set(tmp) if len(tmp) < len(opposite) else opposite
            opposite = opposite if len(tmp) < len(opposite) else set(tmp)
            
            step += 1
        
        return 0

[LeetCode] 126. Word Ladder II

Problem : https://leetcode.com/problems/word-ladder-ii/

Consider every word in the wordList is a node of a graph. 

On each node, we may replace the letters of the word to find the next words.

The problem equals find the shortest routines from the begin word to the end word in this graph.

The solution includes two steps.  Firstly, use BFS approach to find the shortest routines from begin word to end word. Meanwhile, save the parent of each visited word. Word A is parent of word B if A can transform to B by replacing a letter.  Secondly, reconstruct routines from end word back to begin word by using the saved parent info of words on shortest routines.

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # impossible to transform if endWord is not in wordList.
        if endWord not in wordList: return []
        
        # construct word mask map
        wordMap = defaultdict(list)
        
        for word in wordList:
            for i in range(len(word)):
                mask = word[:i] + "#" + word[i+1:]
                wordMap[mask].append(word) 
        
        # save the previous word was used to transform to current word
        preWord = defaultdict(list)
        
        # save the minimum step to transform to current word
        visited = defaultdict(lambda : 2 ** 31 - 1)
        visited[beginWord] = 0
        
        # use bfs to find all possible transformation paths
        step = 1
        queue = deque([beginWord])
        
        while queue:
            found = False
            
            for _ in range(len(queue)):
                word = queue.popleft()

                if word == endWord:
                    found = True

                for i in range(len(word)):
                    mask = word[:i] + "#" + word[i+1:]
                    for nxtWord in wordMap[mask]:
                        if nxtWord == word:
                            # skip the current word
                            continue

                        if visited[nxtWord] < step:
                            # already find the shortest path to nxtWord
                            continue
                        
                        if visited[nxtWord] != step:
                            # find the shortest path to nxtWord
                            visited[nxtWord] = step
                            # add nxtWord to queue if this is the first time we reach to it
                            queue.append(nxtWord)
                        
                        # save the previous word of nxtWord
                        preWord[nxtWord].append(word)
            
            step += 1
            if found:
                break
            
        # there is no way to reach to endWord
        if not preWord[endWord]:
            return []
        
        # use dfs to construct the transformation path
        result = []
        stack = []
        stack.append((endWord, [endWord]))
        
        while stack:
            word, tmp = stack.pop()
            
            if word == beginWord:
                result.append(tmp[::-1])
            else:
                for pre in preWord[word]:
                    stack.append((pre, tmp + [pre]))
        
        return result

Edited on 06/19/2021. Optimize performance.

Edited on 07/24/2021. Optimize performance.

[LeetCode] 116. Populating Next Right Pointers in Each Node

Problem : https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

BFS solution :

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        
        
        queue = deque([root])
        
        while queue:
            level = deque()
            
            while queue:
                node = queue.popleft()
                
                if node.left:
                    level.append(node.left)
                
                if node.right:
                    level.append(node.right)
            
            for i in range(1, len(level)):
                level[i-1].next = level[i]
                
            queue = level
        
        
        return root

Recursive solution:

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root != null) {
            if (root.left != null) {
                root.left.next = root.right;
            }
        
            if (root.right != null && root.next != null) {
                root.right.next = root.next.left;
            }
        
            connect(root.right); 
            connect(root.left);
        }
        
        return root;
    }
}

Iterative solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        tmp = root
        while root and root.left:
            nxt = root.left
            
            while root:
                root.left.next = root.right
                root.right.next = root.next.left if root.next else None
                root = root.next
            root = nxt
        
        return tmp

Edited on 12/29/2021. Replace the recursive solution with Java code solution.

[LeetCode] 111. Minimum Depth of Binary Tree

Problem : https://leetcode.com/problems/minimum-depth-of-binary-tree/

DFS solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        
        if root.left:
            return self.minDepth(root.left) + 1
        
        if root.right:
            return self.minDepth(root.right) + 1
        
        return 1

BFS Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        
        level = 0
        queue = deque([root]) if root else deque()
        
        while queue:
            tmp = deque()
            level += 1
            while queue:
                node = queue.popleft()
                
                if not node.left and not node.right:
                    return level
                
                if node.left:
                    tmp.append(node.left)
                
                if node.right:
                    tmp.append(node.right)
            
            queue = tmp
        
        return level

[LeetCode] 107. Binary Tree Level Order Traversal II

Problem : https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

Use BFS traverse the given tree and record the passed node values.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        # bfs
        queue = deque([root])
        result = []
        
        while queue:
            level = deque()
            tmp = []
            
            while queue:
                node = queue.popleft()
                
                tmp.append(node.val)
                
                if node.left:
                    level.append(node.left)
                    
                if node.right:
                    level.append(node.right)
            
            queue = level
            result.insert(0, tmp)
        
        return result

DFS solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        
        # dfs
        result = []
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
            
            if node.right:
                stack.append((node.right, level+1))
            
            if node.left:
                stack.append((node.left, level+1))
        
        return result[::-1]

Edited on 06/06/2021. Add the DFS solution.

[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

Problem : https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Still use BFS approach to traverse the given binary tree. Remember to reverse value order on odd level.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();

        Deque<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offerLast(root);

        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> tmp = new LinkedList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.pollFirst();
                if (level % 2 == 0) {
                    tmp.offerLast(node.val);
                } else {
                    tmp.offerFirst(node.val);
                }
                if (node.left != null) queue.offerLast(node.left);
                if (node.right != null) queue.offerLast(node.right);
            }

            result.add(tmp);

            level += 1;
        }

        return result;
    }
}

DFS solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        dfs(root, 0);
        return result;
    }

    void dfs(TreeNode node, int level) {
        if (node == null) return;

        if (level == result.size()) {
            result.add(new LinkedList<>());
        }

        if (level % 2 == 0) {
            ((LinkedList<Integer>)result.get(level)).offerLast(node.val);
        } else {
            ((LinkedList<Integer>)result.get(level)).offerFirst(node.val);
        }

        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

Edited on 06/06/2021. Add the DFS solution

Edited on 02/18/2023. Replace with Java version BFS & DFS solution

[LeetCode] 102. Binary Tree Level Order Traversal

Problem : https://leetcode.com/problems/binary-tree-level-order-traversal/

Use BFS to traverse the given binary tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        
        if not root:
            return []
        
        result = [] 
        queue = deque([root])
        
        # bfs
        while queue:
            level = deque()
            result.append([])
            
            while queue:
                node = queue.popleft()
                
                result[-1].append(node.val)
                
                if node.left:
                    level.append(node.left)
                    
                if node.right:
                    level.append(node.right)
            
            queue = level
        
        return result

Recursive DFS solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        def dfs(level, node):
            if node:
                yield (level, node.val)
                yield from dfs(level + 1, node.left)
                yield from dfs(level + 1, node.right)
        
        result = []
        
        for level, val in dfs(0, root):
            if level >= len(result):
                result.append([val])
            else:
                result[level].append(val)
        
        return result

Iterative DFS solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        
        stack = [(0, root)] if root else []
        
        while stack:
            level, node = stack.pop()
            
            if level >= len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
        
            if node.right:
                stack.append((level + 1, node.right))
            
            if node.left:
                stack.append((level + 1, node.left))
            
        return result

Edited on 04/21/2021. Add resursive and iterative DFS solution.