【Leetcode】104. Maximum Depth of Binary Tree

Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

DFS with Recursion

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val)
#         @val = val
#         @left, @right = nil, nil
#     end
# end

# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
    root.nil?? 0 : [max_depth(root.left), max_depth(root.right)].max + 1
end

BFS

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val)
#         @val = val
#         @left, @right = nil, nil
#     end
# end

# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
  depth = 0
  tree = []

  tree << root unless root.nil?

  while !tree.empty?
    depth += 1


    n = tree.size - 1

    for i in 0..n
      node = tree.shift
      tree << node.left  unless node.left.nil?
      tree << node.right unless node.right.nil?
    end
  end

  depth
end

DFS

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val)
#         @val = val
#         @left, @right = nil, nil
#     end
# end

# @param {TreeNode} root
# @return {Integer}
def max_depth(root)
  tree = []
  res  = []

  unless root.nil?
    tree << root
    res  << 1
  end

  max = 0
  while !tree.empty?
    node = tree.pop
    tmp  = res.pop
    max  = [max, tmp].max if node.right.nil? && node.left.nil?

    if node.right.present?
      tree << node.right
      res  << tmp + 1
    end

    if node.left.present?
      tree << node.left
      res  << tmp + 1
    end
  end

  max
end