先序遍历

题目描述：给定一个二叉树，返回它的前序（先序）遍历序列。 示例: 输入: [1,null,2,3]

  1. 1   
  2.  \   
  3.   2   
  4.  /  
  5. 3

输出: [1,2,3] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {number[]}
  4.  */
  5. const preorderTraversal = function(root) {
  6.   // 定义结果数组
  7.   const res = []  
  8.   // 处理边界条件
  9.   if(!root) {
  10.       return res
  11.   }
  12.   // 初始化栈结构
  13.   const stack = [] 
  14.   // 首先将根结点入栈
  15.   stack.push(root)  
  16.   // 若栈不为空，则重复出栈、入栈操作
  17.   while(stack.length) {
  18.       // 将栈顶结点记为当前结点
  19.       const cur = stack.pop() 
  20.       // 当前结点就是当前子树的根结点，把这个结点放在结果数组的尾部
  21.       res.push(cur.val)
  22.       // 若当前子树根结点有右孩子，则将右孩子入栈
  23.       if(cur.right) {
  24.           stack.push(cur.right)
  25.       }
  26.       // 若当前子树根结点有左孩子，则将左孩子入栈
  27.       if(cur.left) {
  28.           stack.push(cur.left)
  29.       }
  30.   }
  31.   // 返回结果数组
  32.   return res
  33. };

后序遍历

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {number[]}
  4.  */
  5. const postorderTraversal = function(root) {
  6.   // 定义结果数组
  7.   const res = []  
  8.   // 处理边界条件
  9.   if(!root) {
  10.       return res
  11.   }
  12.   // 初始化栈结构
  13.   const stack = [] 
  14.   // 首先将根结点入栈
  15.   stack.push(root)  
  16.   // 若栈不为空，则重复出栈、入栈操作
  17.   while(stack.length) {
  18.       // 将栈顶结点记为当前结点
  19.       const cur = stack.pop() 
  20.       // 当前结点就是当前子树的根结点，把这个结点放在结果数组的头部
  21.       res.unshift(cur.val)
  22.       // 若当前子树根结点有左孩子，则将左孩子入栈
  23.       if(cur.left) {
  24.         stack.push(cur.left)
  25.       }  
  26.       // 若当前子树根结点有右孩子，则将右孩子入栈
  27.       if(cur.right) {
  28.         stack.push(cur.right)
  29.       }
  30.   }
  31.   // 返回结果数组
  32.   return res
  33. };

中序遍历

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {number[]}
  4.  */
  5. const inorderTraversal = function(root) {
  6.   // 定义结果数组
  7.   const res = []  
  8.   // 初始化栈结构
  9.   const stack = []   
  10.   // 用一个 cur 结点充当游标
  11.   let cur = root  
  12.   // 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
  13.   while(cur || stack.length) {
  14.       // 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来 
  15.       while(cur) {
  16.           // 将途径的结点入栈
  17.           stack.push(cur)  
  18.           // 继续搜索当前结点的左孩子
  19.           cur = cur.left  
  20.       }
  21.       // 取出栈顶元素
  22.       cur = stack.pop()  
  23.       // 将栈顶元素入栈
  24.       res.push(cur.val)  
  25.       // 尝试读取 cur 结点的右孩子
  26.       cur = cur.right
  27.   }
  28.   // 返回结果数组
  29.   return res
  30. };

层序遍历的衍生问题

题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 示例： 二叉树：[3,9,20,null,null,15,7],

  1. 3
  2.  / \
  3. 9  20
  4.   /  \
  5.  15   7

返回其层次遍历结果： [ [3], [9,20], [15,7] ]

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {number[][]}
  4.  */
  5. const levelOrder = function(root) {
  6.     // 初始化结果数组
  7.     const res = []  
  8.     // 处理边界条件
  9.     if(!root) {
  10.         return res
  11.     }  
  12.     // 初始化队列
  13.     const queue = []   
  14.     // 队列第一个元素是根结点
  15.     queue.push(root)  
  16.     // 当队列不为空时，反复执行以下逻辑
  17.     while(queue.length) {
  18.         // level 用来存储当前层的结点
  19.         const level = []  
  20.         // 缓存刚进入循环时的队列长度，这一步很关键，因为队列长度后面会发生改变
  21.         const len = queue.length  
  22.         // 循环遍历当前层级的结点
  23.         for(let i=0;i<len;i++) {
  24.             // 取出队列的头部元素
  25.             const top = queue.shift()  
  26.             // 将头部元素的值推入 level 数组
  27.             level.push(top.val)
  28.             // 如果当前结点有左孩子，则推入下一层级
  29.             if(top.left) {
  30.                 queue.push(top.left)
  31.             }
  32.             // 如果当前结点有右孩子，则推入下一层级
  33.             if(top.right) {
  34.                 queue.push(top.right)
  35.             }
  36.         }
  37.         // 将 level 推入结果数组
  38.         res.push(level)
  39.     }
  40.     // 返回结果数组
  41.     return res
  42. };

翻转二叉树

题目描述：翻转一棵二叉树。


示例： 输入：

  1.      4
  2.    /   \
  3.   2     7
  4.  / \   / \
  5. 1   3 6   9

输出：

  1.      4
  2.    /   \
  3.   7     2
  4.  / \   / \
  5. 9   6 3   1

  1. /**
  2.  * @param {TreeNode} root
  3.  * @return {TreeNode}
  4.  */
  5. const invertTree = function(root) {
  6.     // 定义递归边界
  7.     if(!root) {
  8.         return root;
  9.     }
  10.     // 递归交换右孩子的子结点
  11.     let right = invertTree(root.right);
  12.     // 递归交换左孩子的子结点
  13.     let left = invertTree(root.left);
  14.     // 交换当前遍历到的两个左右孩子结点
  15.     root.left = right;
  16.     root.right = left;
  17.     return root;
  18. };