[LeetCode] 394. Decode String

 Problem : https://leetcode.com/problems/decode-string/

Use 2 stacks to decode. One stack save the counter. Another stack save of the decoded string of current level.

Time Complexity = O ( N * K ),  N = length of the input string. K = maximum value of the counter .

class Solution {
    public String decodeString(String s) {
        // save the decoded string
        // use StringBuilder to avoid repeatedly creating string object
        Stack<StringBuilder> strStack = new Stack();
        // save the counter of decoded string
        Stack<Integer> counterStack = new Stack();
        
        strStack.push(new StringBuilder());
        int count = 0;
        
        for (Character a: s.toCharArray()) {            
            if (Character.isDigit(a)) {
                // important!  counter k may have more than one digits!
                count = count * 10 + (a - '0');
            } else if (a == '[') {
                // push the counter
                counterStack.push(count);
                // push a new string builder to start a new level
                strStack.push(new StringBuilder());
                // reset the counter
                count = 0;
            } else if (a == ']') {
                // current level decoded string
                String decoded = strStack.pop().toString(); 
                // count of current level decoded string
                int n = counterStack.pop();
                
                // append the decoded string to its upper level string
                for (int j = 0; j < n; j++) {
                    strStack.peek().append(decoded);
                }
            } else {
                // append the character to current level string
                strStack.peek().append(String.valueOf(a));
            }
        }
        
        return strStack.peek().toString();
    }
}

[LeetCode] 430. Flatten a Multilevel Doubly Linked List

 Problem : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

 Use stack to mimic DFS

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head: return None
        
        dummy = Node()
        p = dummy
        
        stack = [head]
        
        while stack:
            h = stack.pop()
            
            while h:
                p.next = h
                h.prev = p
                p = p.next
                    
                if h.child:
                    if h.next:
                        stack.append(h.next)
                    
                    tmp = h.child
                    h.child = None
                    h = tmp
                else:
                    h = h.next
                
        
        dummy.next.prev = None
        return dummy.next

[LeetCode] 1586. Binary Search Tree Iterator II

 Problem : https://leetcode.com/problems/binary-search-tree-iterator-ii/

Use another stack to save the previous nodes while iterating through in-order traversal.

# 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 BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.pre = []
        
        while root:
            tmp = root.left
            root.left = None
            self.stack.append(root)
            root = tmp
            

    def hasNext(self) -> bool:
        return len(self.stack) > 0
        
    def next(self) -> int:
        node = self.stack.pop()
        self.pre.append(node)
        
        if node.right:
            tmp = node.right
            node.right = None
            
            node = tmp
            
            while node:
                tmp = node.left
                node.left = None
                self.stack.append(node)
                node = tmp
        
        return self.pre[-1].val
    
    def hasPrev(self) -> bool:
        return len(self.pre) >= 2
        

    def prev(self) -> int:
        node = self.pre.pop()
        self.stack.append(node)
        return self.pre[-1].val


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.hasNext()
# param_2 = obj.next()
# param_3 = obj.hasPrev()
# param_4 = obj.prev()

[LeetCode] 921. Minimum Add to Make Parentheses Valid

 Problem : https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

Use stack to match left parenthesis with right parenthesis as much as possible.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        
        for w in s:
            if w == '(':
                stack.append(w)
            elif stack and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(w)
        
        return len(stack)

[LeetCode] 388. Longest Absolute File Path

 Problem : https://leetcode.com/problems/longest-absolute-file-path/

Use two pointers approach to parse directory / file name.

Use stack to maintain the paths to current files. We need to pop directory from stack is depth of current file is less than the directory on the top of the stack.

Time Complexity = O ( N ).   N = len(input).  As the code only visit each character in the input once.

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        if not input: return 0 
        
        result = 0
        
        # Stack<[fileName, depth]>
        stack = []
            
        left = right  = 0
        depth = 0
        
        while right < len(input):
            if input[right] == '\n' or right == len(input) - 1:
                # pop back to the depth of current file
                while stack and stack[-1][1] >= depth:
                    stack.pop()
                
                # find current file name
                file = input[left:right] if input[right] == '\n' else input[left:right+1]
                stack.append([file, depth])
                
                # calculate the full path to a file
                if '.' in input[left:right]:
                    paths = '/'.join([a for a, _ in stack])
                    result = max(result, len(paths))
                
                # calculate next depth
                right += 1
                left = right
                depth = 0
                
                while right < len(input) and input[right] == '\t':
                    depth += 1
                    right += 1
                
                left = right
            else:
                right += 1
        
        return result

[LeetCode] 385. Mini Parser

 Problem : https://leetcode.com/problems/mini-parser/

Time Complexity = O (N ** 2)

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        if not s: return NestedInteger()
           
        if s[0] != '[': return NestedInteger(int(s))
        
        if len(s) <= 2: return NestedInteger()
        
        result = NestedInteger()
        
        left = 1
        lb = rb = 0
        
        for right in range(1, len(s)):
            if s[right] == '[':
                lb += 1
            elif s[right] == ']':
                rb += 1
                
            if (lb == rb and s[right] == ',') or right == len(s) - 1:
                result.add(self.deserialize(s[left:right]))
                left = right + 1
                
        return result

[LeetCode] 341. Flatten Nested List Iterator

 Problem : https://leetcode.com/problems/flatten-nested-list-iterator/

Use stack to cache the expanded lists.

Must filter out the empty nested lists in hasNext() method.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        for n in reversed(nestedList):
            self.stack.append(n)
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
        
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            # expand non-empty nested list
            nestedList = self.stack.pop().getList()
            if nestedList:
                for n in reversed(nestedList):
                    self.stack.append(n)

        return self.stack
         

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Another approach of using stack. It's similar to how compiler maintains call-stack.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = [[nestedList, 0]]
    
    def next(self) -> int:
        nlist, nindex = self.stack[-1]
        
        self.stack[-1][1] += 1
        return nlist[nindex].getInteger()
        
    
    def hasNext(self) -> bool:     
        while self.stack:
            nlist, nindex = self.stack[-1]

            if nindex == len(nlist):
                self.stack.pop()
                continue

            if nlist[nindex].isInteger():
                break

            self.stack[-1][1] += 1
            childList = nlist[nindex].getList()
            if childList:
                self.stack.append([childList, 0])
        
        return self.stack
         

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Edited on 04/13/2021. Add the second stack based approach.

[LeetCode] 232. Implement Queue using Stacks

Problem : https://leetcode.com/problems/implement-queue-using-stacks/

Use 2 stacks

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        result = 0
        tmp = []
        while len(self.stack) > 1:
            tmp.append(self.stack.pop())
        
        result = self.stack.pop()
        while tmp:
            self.stack.append(tmp.pop())
        
        return result
        

    def peek(self) -> int:
        """
        Get the front element.
        """
        result = 0
        tmp = []
        while len(self.stack) > 1:
            tmp.append(self.stack.pop())
        
        result = self.stack[0]
        while tmp:
            self.stack.append(tmp.pop())
        
        return result
        

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.stack) == 0
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

[LeetCode] 227. Basic Calculator II

Problem : https://leetcode.com/problems/basic-calculator-ii/

Use stack to postpone the operator evaluation.

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        
        int num = 0;
        Character opt = '+'; 
            
        for (int i = 0; i <= s.length(); i++) {
            if (i == s.length() || s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/') {
                if (opt == '+') {
                    stack.push(num);
                } else if (opt == '-') {
                    stack.push(-1 * num);
                } else if (opt == '*') {
                    stack.push(stack.pop() * num);
                } else if (opt == '/') {
                    stack.push(stack.pop() / num);
                }
                
                opt = i < s.length() ? s.charAt(i) : '+';
                num = 0;
                
            } else if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
        }
        
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }
}

Edited on 12/24/2021. Updated for a simpler stack based solution.

[LeetCode] 225. Implement Stack using Queues

Problem : https://leetcode.com/problems/implement-stack-using-queues/

Use 2 queues in turn to save items.

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.q1 = deque()
        self.q2 = deque()
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        
        # use empty queue to save item
        if self.q1:
            self.q1.append(x)
        else:
            self.q2.append(x)
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        
        # push items to the empty queue, then pop the last item
        if self.q1:
            while len(self.q1) != 1:
                self.q2.append(self.q1.popleft())
            return self.q1.popleft()
        else:
            while len(self.q2) != 1:
                self.q1.append(self.q2.popleft())
            return self.q2.popleft()

    def top(self) -> int:
        """
        Get the top element.
        """
        # return the last item of the non-empty queue
        if self.q1:
            return self.q1[-1]
        else:
            return self.q2[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        
        # stack is empty if both queue is empty
        return len(self.q1) == 0 and len(self.q2) == 0
        


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

[LeetCode] 224. Basic Calculator

Problem : https://leetcode.com/problems/basic-calculator/

The expression does not include multiplication and division operator. We can calculate the result directly.

When we encounter left-parenthesis, we push current result to stack and restart calculation of the interim expression.

Time complexity = O ( N )

class Solution:
    def calculate(self, s: str) -> int:
        stackSign = [1]
        stackNum = [0]
 
        i = 0
        sign = 1
      
        while i < len(s):
            if s[i] == ' ':
                i += 1
                continue
            
            if s[i] == '-':
                sign = -1
                i += 1
                continue
                
            if s[i] == '+':
                sign = 1
                i += 1
                continue
                
            if s[i] == '(':
                stackSign.append(sign)
                stackNum.append(0)
                sign = 1 # reset the sign for expression in bracket
                i += 1
                continue
                
            if s[i] == ')':
                tmp = stackSign.pop() * stackNum.pop() 
                stackNum[-1] += tmp
        
                i += 1
                continue
            
            num = 0
            
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            
            stackNum[-1] += sign * num
        
        return stackSign[-1] * stackNum[-1]

Edited on 09/11/2021. Simplify the stack based solution.

[LeetCode] 173. Binary Search Tree Iterator

Problem : https://leetcode.com/problems/binary-search-tree-iterator/

Because in-order traverse BST can generate a ascending sequence.

# 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 BSTIterator:

    def __init__(self, root: TreeNode):
        
        def inorder(node):
            if node:
                yield from inorder(node.right)
                yield node.val
                yield from inorder(node.left)
        
        self.nodes = list(inorder(root))

    def next(self) -> int:
        return self.nodes.pop()

    def hasNext(self) -> bool:
        return self.nodes


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

A stack based iterative 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 BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = [root] if root else []
        

    def next(self) -> int:
        node = self.stack[-1]
        
        while node.left:
            self.stack.append(node.left)
            tmp = node.left
            node.left = None
            node = tmp
        
        # pop the parent node
        self.stack.pop()
        
        if node.right:
            self.stack.append(node.right)
            node.right = None
        
        return node.val
        

    def hasNext(self) -> bool:
        return self.stack
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Edited on 04/22/2021. Refactor the recursive and iterative solution.

[LeetCode] 155. Min Stack

Problem : https://leetcode.com/problems/min-stack/

Should save current minimum value in stack for O(1) time complexity.

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        if len(self.stack) == 0:
            self.stack.append({'value': x, 'min': x})
        else:
            self.stack.append({'value': x, 'min': min(x, self.stack[-1]['min'])})
        
    def pop(self) -> None:
        del self.stack[-1]

    def top(self) -> int:
        return self.stack[-1]['value']
        

    def getMin(self) -> int:
        return self.stack[-1]['min']


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

[LeetCode] 150. Evaluate Reverse Polish Notation

Problem : https://leetcode.com/problems/evaluate-reverse-polish-notation/

Use stack to cache operand and operator.

In python,  6 / -132 = -1.  To get the same result as C division operator, use int( 6 / -132 ) instead.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        
        operators = { '+' : lambda a, b: a + b,    \
                      '-' : lambda a, b: a - b,    \
                      '*' : lambda a, b: a * b,    \
                      '/' : lambda a, b: int(a/b) }
        
        for t in tokens:
            opt = operators.get(t)
            if opt:
                b = stack.pop()
                a = stack.pop()
                
                c = opt(a, b)
                stack.append(c)
            else:
                stack.append(int(t))
    
        return stack.pop()

Edited on 05/25/2021. Simplify condition checks.

[LeetCode] 145. Binary Tree Postorder Traversal

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

Recursive 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 postorderTraversal(self, root: TreeNode) -> List[int]:
        
        def postorder(node):
            if node:
                yield from postorder(node.left)
                yield from postorder(node.right)
                yield node.val
        
        return list(postorder(root))

Iterative 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 postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack[-1]
            
            if not node.left and not node.right:
                result.append(node.val)
                stack.pop()
            else:
                if node.right:
                    stack.append(node.right)
                    node.right = None

                if node.left:
                    stack.append(node.left)
                    node.left = None

        return result

Edited on 04/20/2021. Add the recursive approach.

Edited on 04/20/2021. Update the stack based iterative approach.

[LeetCode] 144. Binary Tree Preorder Traversal

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

Recursive 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(node):
            if node:
                yield node.val
                yield from preorder(node.left)
                yield from preorder(node.right)

        return list(preorder(root))

Iterative 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack.pop()
            
            result.append(node.val)
            
            for child in filter(None, [node.right, node.left]):
                stack.append(child)
        
        return result

Edited on 04/20/2021. Update iterative solution. Same approach can apply to N-array tree too.

Edited on 04/20/2021. Update recursive solution. Use 'yield' and 'yield from'.

[LeetCode] 143. Reorder List

Problem : https://leetcode.com/problems/reorder-list/

Construct the needed list by doing preorder and postorder traversal at the same time.

Time Complexity = O ( N )

Space Complexity =  O ( 1 ) 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
        self.dummy = ListNode()
        self.p = self.dummy
        
        self.preorder = head
        self.seen = set()
        
        def postorder(node):
            if node:
                postorder(node.next)
                
                # add node by preorder traversal
                if self.preorder not in self.seen:
                    self.seen.add(self.preorder)
                    
                    self.p.next = self.preorder
                    self.preorder = self.preorder.next

                    self.p = self.p.next
                
                # add node by postorder traversal
                if node not in self.seen:
                    self.seen.add(node)
                    
                    self.p.next = node
                    self.p = self.p.next
        
        postorder(head)
        
		# end the list
        self.p.next = None

A stack based solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head: return
        
        stack = []
        
        p = head
        total = 0
        
        while p:
            stack.append(p)
            p = p.next
            total += 1
        
        total = total // 2
        
        p = head
        while total > 0:
            tmp = p.next
            p.next = stack.pop()
            total -= 1
            
            p = p.next
            p.next = tmp
            p = p.next
            
        
        p.next = None

An iterative solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode p1 = head;  // slow
        ListNode p2 = head;  // fast
        
        // find the middle node
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        
        ListNode mid = p1.next;
        p1.next = null;
        
        // return directly if the second half list is empty
        if (mid == null) {
            return;
        }
        
        // reverse the second half list
        ListNode pre = null;
        ListNode cur = mid;
        
        while (cur.next != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        cur.next = pre;
        
        // reorder the list
        p1 = head;
        p2 = cur;
        
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        
        while (p1 != null || p2 != null) {
            
            if (p1 != null) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }
            
            if (p2 != null) {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
    }
}

Edited on 12/21/2021. Add the iterative solution.

[LeetCode] 129. Sum Root to Leaf Numbers

Problem : https://leetcode.com/problems/sum-root-to-leaf-numbers/

Use DFS approach to travel from root to every leafs.

A rescurisve approach:

Time Complexity = O ( N )

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode node, int tmp) {
        tmp = tmp  * 10 + node.val;
        if (node.left == null && node.right == null) {
            return tmp;
        }

        int result = 0; 
        result += (node.left != null) ? dfs(node.left, tmp) : 0;
        result += (node.right != null) ? dfs(node.right, tmp) : 0;
        return result;
    }
}

An iterative approach:

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 sumNumbers(self, root: TreeNode) -> int:
        result = 0
        stack = [(0, root)]
        
        while stack:
            num, node = stack.pop()
            num =  num * 10 + node.val
            
            if not node.left and not node.right:
                result += num
            else:
                if node.right:
                    stack.append((num, node.right))
                if node.left:
                    stack.append((num, node.left))
        
        return result

Edited on 03/13/2023. Replace the recursive solution with a Java based solution.

Edited on 04/24/2021. Refactor the recursive solution.

Edited on 04/24/2021. Add the iterative solution.

[LeetCode] 104. Maximum Depth of Binary Tree

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

Calculate depth recursively.

# 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 maxDepth(self, root: TreeNode) -> int:
        if root:
            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
        
        return 0

A iterative 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 maxDepth(self, root: TreeNode) -> int:
        result = 0
        stack = [(1, root)] if root else []
        
        while stack:
            level, node = stack.pop()
            
            if not node.left and not node.right:
                result = max(result, level)
            else:
                if node.right:
                    stack.append(((level + 1), node.right))
                if node.left:
                    stack.append(((level + 1, node.left)))
        
        return result

Edited on 04/24/2021. Add the iterative 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.