跳到主要内容

操作

一、前序遍历​

1.1 递归​

思路: 定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

实现

function preorderTraversal(root) {
  const result = [];
  const preorder = (root) => {
    if (root == null) {
      return;
    }
    result.push(root.val);
    preorder(root.left);
    preorder(root.right);
  };
  preorder(root);
  return result;
}

1.2 迭代​

思路: 区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来

实现

function preorderTraversal(root) {
  if (root == null) {
    return [];
  }
  const result = [];
  const stack = [];
  let current = root;
  while (stack.length !== 0 || current != null) {
    while (current != null) {
      result.push(current.val);
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    current = current.right;
  }
  return result;
}

二、中序遍历​

2.1 递归​

思路 定义 inorder(root) 表示当前遍历到 root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树，然后将 root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

实现

function inorderTraversal(root) {
  const result = [];
  const inorder = (root) => {
    if (!root) {
      return;
    }
    inorder(root.left);
    result.push(root.val);
    inorder(root.right);
  };
  inorder(root);
  return result;
}

2.2 迭代​

思路: 方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同

实现

function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current != null || stack.length !== 0) {
    while (current != null) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}

三、后序遍历​

3.1 递归​

思路: 定义 postorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要递归调用 postorder(root->left) 来遍历 root 节点的左子树，然后递归调用 postorder(root->right) 来遍历 root 节点的右子树，最后将 root 节点的值加入答案即可，递归终止的条件为碰到空节点。

实现

function postorderTraversal(root){
  const result = [];
  const postorder = (root)=>{
    if(root == null){
      return 
    }
    postorder(root.left);
    postorder(root.right);
    result.push(root.val);
  }
  postorder(root);
  return result;
}

3.2 迭代​

思路: 我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同

实现

function postorderTraversal(root) {
  const result = [];
  const stack = [];
  if (root == null) {
    return [];
  }
  let current = root;
  let prev = null;
  while (current != null || stack.length !== 0) {
    while (current != null) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    if (current.right == null || current.right == prev) {
      result.push(current.val);
      prev = current;
      current = null;
    } else {
      stack.push(current);
      current = current.right;
    }
  }
  return result;
}

四、层序遍历​

4.1 广度优先搜索​

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例1:

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例2:

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

思路

实现

function levelOrder(root) {
  const result = [];
  if (root == null) {
    return result;
  }
  const levelList = [];
  levelList.push(root);
  while (levelList.length !== 0) {
    const levelListSize = levelList.length;
    result.push([]);
    for (let i = 1; i <= levelListSize; i++) {
      const node = levelList.shift();
      result[result.length - 1].push(node.val);
      if (node.left) {
        levelList.push(node.left);
      }
      if (node.right) {
        levelList.push(node.right);
      }
    }
  }
  return result;
}

五、之字遍历​

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

示例1:

输入：{1,2,3,#,#,4,5}
返回值：[[1],[3,2],[4,5]]
说明：如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。

示例2:

输入： {8,6,10,5,7,9,11}
返回值：[[8],[10,6],[5,7,9,11]]

六、最大深度​

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

6.1 深度优先搜索​

思路: 如果我们知道了左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为 max(l,r)+1。而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。

实现

function maxDepth(root) {
  if (root == null) {
    return 0;
  } else {
    let leftHeight = maxDepth(root.left);
    let rightHeight = maxDepth(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
  }
}

6.2 广度优先搜索​

思路: 我们也可以用「广度优先搜索」的方法来解决这道题目，但我们需要对其进行一些修改，此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展，最后我们用一个变量 ans 来维护拓展的次数，该二叉树的最大深度即为 ans。

实现

function maxDepth(root) {
  if (root == null) {
    return 0;
  }
  const queue = [];
  queue.push(root);
  let result = 0;
  while (queue.length !== 0) {
    let length = queue.length;
    while (length > 0) {
      let node = queue.shift();
      if (node.left != null) {
        queue.push(node.left);
      }
      if (node.right != null) {
        queue.push(node.right);
      }
      length--;
    }
    result++;
  }
  return result;
}

七、二叉树中和为某一值的路径​

给你二叉树的根节点 root 和一个整数目标和 targetSum,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

示例1:

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例2:

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

7.1 深度优先搜索​

思路: 我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

实现

function pathSum(root, target) {
  let result = [];
  let path = [];
  const dfs = (root, target) => {
    if (root == null) {
      return;
    }
    path.push(root.val);
    target -= root.val;
    if (root.left == null && root.right == null && target == 0) {
      result.push([...path]);
    }
    dfs(root.left, target);
    dfs(root.right, target);
    path.pop();
  };
  dfs(root, target);
  return result;
}

7.2 广度优先搜索​

思路: 我们也可以采用广度优先搜索的方式，遍历这棵树。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。为了节省空间，我们使用哈希表记录树中的每一个节点的父节点。每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。

实现

八、翻转二叉树​

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例1:

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例2:

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

8.1 递归​

思路: 从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转

实现

function invertTree(root){
    if(root == null){
        return null;
    }
    let left = invertTree(root.left);
    let right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}