二叉树的遍历

lc144. 二叉树的前序遍历简单 hot

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

法一： 递归

思路很简单就是先递归遍历左子树再遍历右子树

时间复杂度O(n)

空间复杂度O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
 
var preorderTraversal = function(root) {
  let result = []
  const childNode = (node) => {
    if(node) {
      result.push(node.val)
        childNode(node.left)
        childNode(node.right)
      // 同样的，中序遍历则是先left 再push 再right 
      // 后序遍历则是 先left 后right 再push
      }
    }
  childNode(root)
  return result
};

法二：迭代

用栈来模拟递归

• 维护一个栈数组和一个结果数组

• 首先根节点入栈

• 由于栈是后进先出

• 首先根节点出栈，将根节点的值放在结果数组中

• 如果该根节点存在右节点，让右节点入栈

• 接着如果该根节点存在左节点，左节点入栈

var preorderTraversal = function(root) {
    const stack = []
    const list = []
    if(root) stack.push(root)
    while(stack.length > 0) {
        const curNode = stack.pop()
        list.push(curNode.val)
        if(curNode.right) stack.push(curNode.right)
        if(curNode.left) stack.push(curNode.left)
    }
    return list
};
// 中序遍历
var inorderTraversal = function(root) {
  	const stack = []
    const list = []
    while(stack.length || root) {
        while(root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        list.push(root.val)
        root = root.right
    }
    return list
}
// 后序遍历
var postorderTraversal = function(root) {
    const stack = []
    const list = []
    let prev = null
    while(stack.length || root) {
        while(root) {
            stack.push(root)
            root = root.left
        }
        // 当root为空时,将上一个节点拿出来进行判断
        root = stack.pop()
        // 如果该节点的右节点是空的代表左右节点都是空,如果 该节点的右节点已经访问过,
        // 说明该节点的左右节点都已经访问过,将该节点存入arr,并且以该节点为prev,
        // 置空root是为了返回到上一步,因为后面的都已经访问过了
        if(!root.right || root.right === prev) {
            list.push(root.val)
            prev = root
            root = null
        }
        // 否则的话,必须将该节点重新入栈,不然下一次这个节点就访问不到了,下次访问其实也就是第二次访问
        else {
            stack.push(root)
            root = root.right
        }
    }
    return list
};
// 还可以这样
var postorderTraversal = function(root) {
  if(!root) return []
  const res = []
  const stack = []
  stack.push(root)
  while(stack.length) {
    let node = stack.pop()
    res.unshift(node.val)
    if(node.left) stack.push(node.left)
    if(node.right) stack.push(node.right)
  }
  return res
}

时间复杂度O(n)

空间复杂度O(n)

lc589. N叉树的前序遍历简单

题目描述

给定一个 N 叉树，返回其节点值的 前序遍历 。

N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

进阶：

递归法很简单，你可以使用迭代法完成此题吗?

示例 1：

输入：root = [1,null,3,2,4,null,5,6]

输出：[1,3,5,6,2,4]

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

// 递归
/**
 * @param {Node|null} root
 * @return {number[]}
 */
var preorder = function(root) {
  const res = []
  const childNode = node => {
    if(node) {
      res.push(node.val)
      node.children.forEach(item => {
        childNode(item)
      })
    }
  }
  childNode(root)
  return res
};

// 迭代
var preorder = function(root) {
 	const stack = []
  const res = []
  if(root) stack.push(root)
  while(stack.length) {
    let node = stack.pop()
    res.push(node.val)
    if(node.children) {
      for(let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i])
      }
    }
  }
  return res
};
// N叉🌲后序遍历
var postorderTraversal = function(root) {
  if(!root) return []
  const res = []
  const stack = []
  stack.push(root)
  while(stack.length) {
    let node = stack.pop()
    res.unshift(node.val)
    if(node.children) {
      stack.push(...node.children)
    }
  }
  return res
};

lc102. 二叉树的层序遍历中等hot

题目描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：

二叉树：[3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

法一：BFS广度优先

思路：

• 每向下一层，然后把他们的值存起来
• 利用了多个数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []
    let queue = [root]
    const res = []
    while(queue.length) {
        let temp = []
        let cur = []
        while(queue.length) {
            let node = queue.shift()
            cur.push(node.val)
            if(node.left) temp.push(node.left)
            if(node.right) temp.push(node.right)
        }
        res.push(cur)
        queue = temp
    }
    return res
};
// 这个比较容易理解
var levelOrder = function(root) {
  if(!root) return []
  const res = []
  const queue = [root]
  let len = 0
  while(queue.length) {
    res[len] = []
    let queuelen = queue.length
    while(queuelen--) {
      let node = queue.shift()
      if(node) {  
        res[len].push(node.val)
        if(node.left) queue.push(node.left)
        if(node.right) queue.push(node.right)
      }
    }
    len++
  }
  return res
};

时间复杂度O(n)

空间复杂度O(n)

法二：DFS深度优先

• 根据树依次向下遍历，并记录每次的depth
• 然后把相应的node.val存到结果数组里面去

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    let res = []
    const dep = function(node, depth) {
        if(!node) return
        res[depth] = res[depth] || []
        res[depth].push(node.val)
        dep(node.left, depth + 1)
        dep(node.right, depth + 1)
    }
    dep(root, 0)
    return res
};

时间复杂度O(n)

空间复杂度O(h) h为树的高度

lc103. 二叉树的锯齿形层序遍历中等hot

题目描述

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

思路

就是从零开始，奇数就从右往左，偶数就从左往右

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    const res = []
    
    function dfs(node, depth){
        if(!node) return 

        if(!Array.isArray(res[depth])){
            res[depth] = []
        }
        // 奇数
        if(depth & 1){
            res[depth].unshift(node.val)
        }else{
            res[depth].push(node.val)
        }
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    }

    dfs(root, 0)
    return res
};

时间复杂度O(n)

空间复杂度O(n)

lc958. 二叉树的完全性检验中等hot

题目描述

给定一个二叉树，确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

示例 1：

输入：[1,2,3,4,5,6]

输出：true

解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

示例 2：

输入：[1,2,3,4,5,null,7]

输出：false

解释：值为 7 的结点没有尽可能靠向左侧。

思路很简单 就是给每个节点一个索引值，假如中间空缺一个节点的话，索引值就对不上号

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function(root) {
  if(!root) return true
  const queue = []
  let index = 0
  queue.push({node: root, index: 1})
  while(queue.length) {
    let cur = queue.shift()
    let node = cur.node
    let i = cur.index
    if(i !== ++index) return false

    node.left && queue.push({node: node.left, index: index * 2})
    node.right && queue.push({node: node.right, index: index * 2 + 1})
  }
  return true
};

时间复杂度O(n)

空间复杂度O(1)只用初始化一个队列 为常数个内存

lc114. 二叉树的展开为链表中等

题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]

输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [0]

输出：[0]

var flatten = function(root) {
  const res = []
  const childNode = node => {
    if(node) {
      res.push(node)
      childNode(node.left)
      childNode(node.right)
    }
  }

  childNode(root)
  for(let i = 0; i < res.length - 1; i++) {
    res[i].left = null
    res[i].right = res[i + 1]
  }
};

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。
• 空间复杂度：O(n)，其中 n 是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n。

129. 求根节点到叶节点数字之和中等hot

题目描述

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

思路：前序遍历

// dfs
var sumNumbers = function(root) {
  let sum = 0
  const preDfs = (node, numStr) => {
    if(!node.left && !node.right) {
      numStr += node.val
      sum += Number(numStr);
      return;
    } else {
      numStr += node.val
    }
    if(node.left) preDfs(node.left, numStr)
    if(node.right) preDfs(node.right, numStr)
  }
  preDfs(root, '')
  return sum
};

// bfs
var sumNumbers = function(root) {
  if(!root) return 0
  let sum = 0
  const stack = [root]
  const numqueue = [root.val]
  while(stack.length) {
    const curNode = stack.pop()
    const curSum = numqueue.pop()
    if(!curNode.left && !curNode.right) {
      sum += curSum
    } else {
      if(curNode.right) {
        stack.push(curNode.right)
        numqueue.push(curSum * 10 + curNode.right.val)
      } 
      if(curNode.left) {
        stack.push(curNode.left)
        numqueue.push(curSum * 10 + curNode.left.val)
      } 
    }
  }
  return sum
};

时间复杂度:O(n)

空间复杂度:O(n)

lc208. 实现 Trie (前缀树)中等hot

题目描述

Trie (opens new window)（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

思路

对插入进行讲解一下

insert之后是这样，最里面有一个end属性，searchPrefix也是一层一层的找

var Trie = function() {
  this.children = {}
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
  let node = this.children
  for(const ch of word) {
    if(!node[ch]) node[ch] = {}
    node = node[ch]
  }
  node.end = true
};

Trie.prototype.prefix = function(prefix){
  let node = this.children; 
  for(let ch of prefix){
    if(!node[ch]) return false; 
    //如果有一个字符直接没访问到，那就中断查找，说明输入的字符不存在，且不会是某个字符串的前缀
    node = node[ch];
  }
  return node; //相当于一直找到了最后一个字符的对象
}

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
   let res = this.prefix(word);
   return res && res.end == true;//如果它是一个完整单词的结果，那么一定会有end属性为true
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
  return Boolean(this.prefix(prefix));
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */