广度优先搜索（层序），深度优先搜索（前序（递归、迭代）、中序（递归、迭代、莫里斯）、后序（递归、迭代））遍历树深度：求解《515. 在每个树行中找最大值》

var largestValues = function(root) {
  if (root === null) return []
  const q = [root], r = []
  let i = 0
  while (i < q.length) {
    let l = q.length, max = Number.MIN_SAFE_INTEGER
    while (i < l) {
      const n = q[i++]
      if (max < n.val) max = n.val
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
    r.push(max)
  } 
  return r
};

function largestValues(root: TreeNode | null): number[] {
  if (root == null) return []
  const q = [root], r = []
  let i = 0
  while (i < q.length) {
    let max = Number.MIN_SAFE_INTEGER
    for (let l = q.length; i < l; i++) {
      const n = q[i]
      if (max < n.val) max = n.val
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
    r.push(max)
  }
  return r
};

func largestValues(root *TreeNode) []int {
  if root == nil {
    return []int{}
  }
  q, r, i := []*TreeNode{root}, []int{}, 0
  for i < len(q) {
    m := ^int(^uint(0) >> 1)
    for l := len(q); i < l; i++ {
      n := q[i]
      if m < n.Val {
        m = n.Val
      }
      if n.Left != nil {
        q = append(q, n.Left)
      }
      if n.Right != nil {
        q = append(q, n.Right)
      }
    }
    r = append(r, m)
  }
  return r
}

class Solution {
  function largestValues($root) {
    if ($root == null) return [];
    $q = [$root];
    $i = 0;
    $r = [];
    while ($i < count($q)) {
      $m = PHP_INT_MIN;
      for ($l = count($q); $i < $l; $i++) {
        $n = $q[$i];
        if ($m < $n->val) $m = $n->val;
        if ($n->left !== null) $q []= $n->left;
        if ($n->right !== null) $q []= $n->right;
      }
      $r []= $m;
    }
    return $r;
  }
}

class Solution {
  public List<Integer> largestValues(TreeNode root) {
    List<Integer> r = new ArrayList<Integer>();
    if (root == null) return r;
    Deque<TreeNode> q = new ArrayDeque<TreeNode>();
    q.offerLast(root);
    while (q.isEmpty() == false) {
      int l = q.size(), max = Integer.MIN_VALUE;
      while (l-- > 0) {
        TreeNode n = q.pollFirst();
        if (max < n.val) max = n.val;
        if (n.left != null) q.offerLast(n.left);
        if (n.right != null) q.offerLast(n.right);
      }
      r.add(max);
    }
    return r;
  }
}

class Solution(object): # Python 2.7
  def largestValues(self, root):
    if root == None: return []
    q, i, r = [root], 0, []
    while i < len(q):
      l, m = len(q), -sys.maxint - 1
      while i < l:
        n = q[i]
        if m < n.val: m = n.val
        if n.left != None: q.append(n.left)
        if n.right != None: q.append(n.right)
        i += 1
      r.append(m)
    return r

class Solution: # Python 3.10
  def largestValues(self, root: Optional[TreeNode]) -> List[int]:
    if root == None: return []
    q, i, r = [root], 0, []
    while i < len(q):
      l, m = len(q), -sys.maxsize - 1
      while i < l:
        n = q[i]
        if m < n.val: m = n.val
        if n.left != None: q.append(n.left)
        if n.right != None: q.append(n.right)
        i += 1
      r.append(m)
    return r

#define MAX(a, b) a > b ? a : b
#define MAX_NODE_SIZE 10000  
int* largestValues(struct TreeNode* root, int* returnSize){
  if (root == NULL) {
    *returnSize = 0;
    return NULL;
  }
  struct TreeNode **q = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * MAX_NODE_SIZE);
  int *r = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
  int head = 0, tail = 0, i = 0;
  q[tail++] = root;
  while (head < tail) {
    int m = INT_MIN;
    for (int l = tail; head < l; head++) {
      struct TreeNode *n = q[head];
      m = MAX(m, n->val);
      if (n->left != NULL) q[tail++] = n->left;
      if (n->right != NULL) q[tail++] = n->right;
    }
    r[i++] = m;
  }
  *returnSize = i;
  return r;
}

class Solution {
public:
  vector<int> largestValues(TreeNode* root) {
    vector<int> r;
    if (root == nullptr) return r;
    queue<TreeNode*> q;
    q.push(root);
    while (q.empty() == false) {
      int l = q.size(), m = INT_MIN;
      while (l--) {
        TreeNode* n = q.front();
        q.pop();
        if (m < n->val) m = n->val;
        if (n->left != nullptr) q.push(n->left);
        if (n->right != nullptr) q.push(n->right); 
      }
      r.push_back(m);
    }
    return r;
  }
};

public class Solution {
  public IList<int> LargestValues(TreeNode root) {
    IList<int> r = new List<int>();
    if (root == null) return r;
    Queue<TreeNode> q = new Queue<TreeNode>();
    q.Enqueue(root);
    while (q.Count > 0) {
      int l = q.Count, m = int.MinValue;
      while (l-- > 0) {
        TreeNode n = q.Dequeue();
        if (m < n.val) m = n.val;
        if (n.left != null) q.Enqueue(n.left);
        if (n.right != null) q.Enqueue(n.right);
      }
      r.Add(m);
    }
    return r;
  }
}

class Solution { // 深度优先搜索 · 中序遍历 · 递归
  private $r = [];
  function largestValues($root) {
    $this->d($root, 0);
    return $this->r;
  }
  function d($n, $depth) {
    if ($n == null) return;
    if ($depth == count($this->r)) $this->r []= PHP_INT_MIN;
    $this->d($n->left, $depth + 1);
    $this->r[$depth] = max($this->r[$depth], $n->val);
    $this->d($n->right, $depth + 1);
  }
}

class Solution { // 深度优先搜索 · 中序遍历 · 递归 · 排序键名
  private $r = [];
  function largestValues($root) {
    $this->d($root, 0);
    ksort($this->r);
    return $this->r;
  }
  function d($n, $depth) {
    if ($n == null) return;
    $this->d($n->left, $depth + 1);
    $this->r[$depth] = max($this->r[$depth] ?? PHP_INT_MIN, $n->val);
    $this->d($n->right, $depth + 1);
  }
}

func largestValues(root *TreeNode) []int { // 深度优先搜索 · 中序遍历 · 单栈 · 哈希映射
  stack, p, r, d := []*TreeNode{}, root, []int{}, map[*TreeNode]int{}
  if root != nil {
    d[root] = 0
    r = append(r, root.Val)
  }
  var update func (n *TreeNode, depth int) 
  update = func(n *TreeNode, depth int) {
    if n != nil {
      if _, ok := d[n]; ok == false {
        d[n] = depth
        if d[n] == len(r) {
          r = append(r, ^int(^uint(0) >> 1))
        }
        r[d[n]] = max(r[d[n]], n.Val); 
      }
    }
  }
  for len(stack) > 0 || p != nil {
    for p != nil {
      stack = append(stack, p)
      update(p.Left, d[p] + 1)
      p = p.Left
    }
    n := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    p = n.Right
    update(p, d[n] + 1)
  }
  return r;
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

func largestValues(root *TreeNode) []int { // 深度优先搜索 · 中序遍历 · 单栈 · 自定义 pair
  type pair struct {
    n *TreeNode
    depth int
  }
  stack, p, r, maxDepth := []pair{}, pair{root, 0}, make([]int, 10000), -1
  for i := 0; i < 10000; i++ {
    r[i] = ^int(^uint(0) >> 1)
  }
  for len(stack) > 0 || p.n != nil {
    for p.n != nil {
      stack = append(stack, pair{p.n, p.depth})
      p = pair{p.n.Left, p.depth + 1}
    }
    n := stack[len(stack) - 1]
    if n.depth > maxDepth {
      maxDepth = n.depth
    }
    if r[n.depth] < n.n.Val {
      r[n.depth] = n.n.Val
    }
    stack = stack[:len(stack) - 1]
    p = pair{n.n.Right, n.depth + 1}
  }
  return r[:maxDepth + 1]
}

class Solution {
public:
  vector<int> largestValues(TreeNode* root) { // 深度优先搜索 · 中序遍历 · 莫里斯遍历
    vector<int> r;
    unordered_map<TreeNode*, int> d;
    if (root) {
      d[root] = 0;
      r.push_back(root->val);
    }
    while (root) {
      int depth = d[root];
      if (root->left) {
        TreeNode* p = root->left;
        while (p->right != nullptr && p->right != root) p = p->right;
        if (p->right == nullptr) {
          p->right = root;
          root = root->left;
        } else {
          p->right = nullptr;
          root = root->right;
        }
      } else {
        root = root->right;
      }
      if (root != nullptr && d.find(root) == d.end()) {
        d[root] = depth + 1;
        if (depth + 1 == r.size()) r.push_back(INT_MIN);
        r[depth + 1] = max(r[depth + 1], root->val);
      }
    }
    return r;
  }
};

class Solution { // 深度优先搜索 · 中序遍历 · 莫里斯遍历 
  public List<Integer> largestValues(TreeNode root) {
    List<Integer> r = new ArrayList<Integer>();
    Map<TreeNode, Integer> d = new HashMap<TreeNode, Integer>();
    if (root != null) {
      d.put(root, 0);
      r.add(root.val);
    }
    while (root != null) {
      int depth = d.get(root);
      if (root.left != null) {
        TreeNode p = root.left;
        while (p.right != null && p.right != root) p = p.right;
        if (p.right == null) {
          p.right = root;
          root = root.left;
        } else {
          p.right = null;
          root = root.right;
        }
      } else {
        root = root.right;
      }
      if (root != null && d.containsKey(root) == false) {
        d.put(root, depth + 1);
        if (depth + 1 == r.size()) r.add(Integer.MIN_VALUE);
        if (r.get(depth + 1) < root.val) r.set(depth + 1, root.val);
      }
    }
    return r;
  }
}

MAX(a, b) a > b ? a : b
MAX_NODE_SIZE 10000
int* largestValues(struct TreeNode* root, int* returnSize){ // 深度优先遍历 · 后序遍历 · 递归
  int *r = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
  *returnSize = 0;
  d(r, returnSize, root, 0);
  return r;
}
void d(int *r, int *i, struct TreeNode* n, int depth) {
  if (n == NULL) return;
  if (depth == *i) r[(*i)++] = INT_MIN;
  d(r, i, n->left, depth + 1);
  d(r, i, n->right, depth + 1);
  r[depth] = MAX(r[depth], n->val);
}

class Solution(object): # Python 2.7
  def largestValues(self, root): # 深度优先搜索 · 后序遍历 · 递归
    r = []
    def d(n, depth):
      if n == None: return
      if depth == len(r): r.append(-sys.maxint - 1)
      d(n.left, depth + 1)
      d(n.right, depth + 1)
      if r[depth] < n.val: r[depth] = n.val
    d(root, 0)
    return r