广度优先搜索（层序），深度优先搜索（前序（递归、迭代）、中序（递归、迭代、莫里斯）、后序（递归、迭代））遍历树深度：求解《513. 找树左下角的值》

var findBottomLeftValue = function(root) {
  const q = [root]
  let n = null
  while (q.length > 0) {
    n = q.shift()
    if (n.right) q.push(n.right)
    if (n.left) q.push(n.left)
  }
  return n.val
};

function findBottomLeftValue(root: TreeNode | null): number {
  const q = [root]
  let n = null
  while (q.length) {
    n = q.shift()
    if (n.right) q.push(n.right)
    if (n.left) q.push(n.left)
  }
  return n.val
};

func findBottomLeftValue(root *TreeNode) int {
  q := []*TreeNode{root}
  var n *TreeNode
  for len(q) > 0 {
    n = q[0]
    q = q[1:]
    if n.Right != nil {
      q = append(q, n.Right)
    }
    if n.Left != nil {
      q = append(q, n.Left)
    }
  }
  return n.Val
}

class Solution {
  function findBottomLeftValue($root) {
    $q = [$root];
    while (count($q)) {
      $n = array_shift($q);
      if ($n->right) $q []= $n->right;
      if ($n->left) $q []= $n->left; 
    }
    return $n->val;
  }
}

class Solution:
  def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
    q, n = [root], None
    while len(q) > 0:
      n = q.pop(0)
      if n.right != None: q.append(n.right)
      if n.left != None: q.append(n.left)
    return n.val

class Solution {
  public int findBottomLeftValue(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<TreeNode>();
    q.offerLast(root);
    TreeNode n = null;
    while (q.isEmpty() == false) {
      n = q.pollFirst();
      if (n.right != null) q.offerLast(n.right);
      if (n.left != null) q.offerLast(n.left);
    }
    return n.val;
  }
}

MAX_NODE_SIZE 10000
int findBottomLeftValue(struct TreeNode* root){
  struct TreeNode *n;
  struct TreeNode** q = (struct TreeNode **)malloc(sizeof(struct TreeNode) * MAX_NODE_SIZE);
  int head = 0, tail = 0;
  q[tail++] = root;
  while (head < tail) {
    n = q[head++];
    if (n->right) q[tail++] = n->right;
    if (n->left) q[tail++] = n->left;
  }
  return n->val;
}

class Solution {
public:
  int findBottomLeftValue(TreeNode* root) {
    TreeNode* n = nullptr;
    queue<TreeNode *> q;
    q.push(root);
    while (q.empty() == false) {
      n = q.front();
      q.pop();
      if (n->right != nullptr) q.push(n->right);
      if (n->left != nullptr) q.push(n->left);
    }
    return n->val;
  }
};

public class Solution {
  public int FindBottomLeftValue(TreeNode root) {
    Queue<TreeNode> q = new Queue<TreeNode>();
    q.Enqueue(root);
    TreeNode n  = null;
    while (q.Count > 0) {
      n = q.Dequeue();
      if (n.right != null) q.Enqueue(n.right);
      if (n.left != null) q.Enqueue(n.left); 
    }
    return n.val;
  }
}

var findBottomLeftValue = function(root) { // 前序遍历 · 单栈
  const stack = [[root, 1]]
  let maxDepth = r = 0
  while (stack.length) {
    const [n, depth] = stack.pop()
    if (maxDepth < depth) {
      r = n.val
      maxDepth = depth
    }
    if (n.right) stack.push([n.right, depth + 1])
    if (n.left) stack.push([n.left, depth + 1])
  }
  return r
};

class Solution {
public:
  int findBottomLeftValue(TreeNode* root) {// 前序遍历 · 单栈
   stack<pair<TreeNode*, int>*> s;
   int r = 0, maxDepth = 0;
   s.push(new pair<TreeNode*, int>{root, 1});
   while (s.empty() == 0) {
     pair<TreeNode*, int> *p = s.top();
     s.pop();
     TreeNode* n = p->first;
     int depth = p->second;
     if (maxDepth < depth) {
       maxDepth = depth;
       r = n->val;
     }
     if (n->right) s.push(new pair<TreeNode*, int>{n->right, depth + 1});
     if (n->left) s.push(new pair<TreeNode*, int>{n->left, depth + 1});
   }
   return r;
  }
};

class Solution {
  public int findBottomLeftValue(TreeNode root) { // 前序遍历 · 单栈
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    Map<TreeNode, Integer> depthMap = new HashMap<TreeNode, Integer>();
    int maxDepth = 0, r = 0;
    stack.push(root);
    depthMap.put(root, 1);
    while (stack.isEmpty() == false) {
      TreeNode n = stack.pop();
      int depth = depthMap.get(n);
      if (maxDepth < depth) {
        maxDepth = depth;
        r = n.val;
      }
      if (n.right != null) {
        stack.push(n.right);
        depthMap.put(n.right, depth + 1);
      }
      if (n.left != null) {
        stack.push(n.left);
        depthMap.put(n.left, depth + 1);
      }
    }
    return r;
  }
}

var findBottomLeftValue = function(root) { // 中序遍历 · 莫里斯
  let r = 0, maxDepth = 0
  root.depth = 1
  while (root) {
    const depth = root.depth
    if (root.left) {
      let p = root.left
      while (p.right !== null && p.right !== root) p = p.right
      if (p.right === null) {
        p.right = root
        root = root.left
      } else {
        if (maxDepth < depth) {
          maxDepth = depth
          r = root.val
        }
        p.right = null
        root = root.right
      }
    } else {
      if (maxDepth < depth) {
        maxDepth = depth
        r = root.val
      }
      root = root.right
    }
    if (root != null && root.depth == void 0) root.depth = depth + 1
  }
  return r
};

class Solution {
  public int findBottomLeftValue(TreeNode root) { // 中序遍历 · 莫里斯
    int maxDepth = 0, r = 0;
    Map<TreeNode, Integer> depthMap = new HashMap<TreeNode, Integer>();
    depthMap.put(root, 1);
    while (root != null) {
      int depth = depthMap.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 {
          if (maxDepth < depth) {
            maxDepth = depth;
            r = root.val;
          }
          p.right = null;
          root = root.right;
        }
      } else {
        if (maxDepth < depth) {
          maxDepth = depth;
          r = root.val;
        }
        root = root.right;
      }
      if (root != null && depthMap.containsKey(root) == false) depthMap.put(root, depth + 1);
    }
    return r;
  }
}