跳到主要内容

二叉树题库

题型一、相同的树​

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例1:

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例2:

输入：p = [1,2], q = [1,null,2]
输出：false

整体思路:

  • 如果两个二叉树都为空，则两个二叉树相同
  • 如果两个二叉树中只有一个为空，则两个二叉树一定不相同

方案A、深度优先遍历​

思路: 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

function isSameTree(p, q) {
    if(!p&&!q){
        return true
    }else if(!p||!q){
        return false;
    }else if(p.val!=q.val){
        return false;
    }else{
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
};

方案B、广度优先遍历​

思路: 通过广度优先搜索判断两个二叉树是否相同。同样首先判断两个二叉树是否为空，如果两个二叉树都不为空，则从两个二叉树的根节点开始广度优先搜索。使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作。

  1. 比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同；

  2. 如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同；

  3. 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。

如果搜索结束时两个队列同时为空，则两个二叉树相同。如果只有一个队列为空，则两个二叉树的结构不同，因此两个二叉树不同。

function isSameTree(p, q) {
    if(!p&&!q){
        return true;
    }else if(!p||!q){
        return false;
    }
    const queueP=[];
    const queueQ=[];
    queueP.push(p);
    queueQ.push(q);
    while(queueP.length&&queueQ.length){
        let nodeP=queueP.shift();
        let nodeQ=queueQ.shift();
        if(nodeP.val!=nodeQ.val){
            return false;
        }
        let leftP=nodeP.left;
        let rightP=nodeP.right;
        let leftQ=nodeQ.left;
        let rightQ=nodeQ.right;
        if(!leftP^!leftQ){
            return false;
        }
        if(!rightP^!rightQ){
            return false;
        }
        if(leftP){
            queueP.push(leftP);
        }
        if(rightP){
            queueP.push(rightP);
        }
        if(leftQ){
            queueQ.push(leftQ);
        }
        if(rightQ){
            queueQ.push(rightQ);
        }
    }
    return !queueP.length&&!queueQ.length;
};

题二、前序遍历​

方案A、递归​

思路: 定义 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;
}

方案B、迭代​

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

实现

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;
}

题三、中序遍历​

方案A、递归​

思路 定义 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;
}

方案B、迭代​

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

实现

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;
}

题四、后序遍历​

方案A、递归​

思路: 定义 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;
}

方案B、迭代​

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

实现

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;
}

题五、层序遍历​

方案A、广度优先搜索​

给你二叉树的根节点 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]]

方案A​