ChoDocs

外观

LeetCode 144. 二叉树的前序遍历 ​

作者:Choi Yang
更新于:17 小时前
字数统计:242 字
阅读时长:1 分钟

题目描述 ​

给定一个二叉树，返回它的 前序 遍历。

示例:

javascript
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

递归解法

javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function preorderTraversal(root) {
  if (!root)
    return []
  const res = []
  const fun = (root) => {
    if (root)
      res.push(root.val)
    root.left && fun(root.left)
    root.right && fun(root.right)
  }
  fun(root)
  return res
}

迭代做法

javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function preorderTraversal(root) {
  if (!root)
    return []
  const res = []
  const queue = [root]
  while (queue.length) {
    let size = queue.length
    while (size--) {
      // 取左孩子
      const node = queue.pop()
      res.push(node.val)
      // 优先放右孩子
      node.right && queue.push(node.right)
      node.left && queue.push(node.left)
    }
  }
  return res
}
javascript
学如逆水行舟，不进则退

Contributors ​

Choi Yang
文章作者：Choi Yang
文章链接：
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ChoDocs！