数据结构：二叉树

发表于 | 分类于

二叉树

每个节点最多有两个子树的树结构，左子树和右子树

1
2
3
4
5
6
7
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

二叉树遍历

  • 广度优先遍历 使用队列
  • 深度优先遍历 使用栈（前序、中序、后序）
广度优先遍历

利用一个数组，先存入根结点，然后依次存入左右节点，每次从头部取出第一个进行操作（越先存入越早取出）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function binaryBFS(root){
  let queue = [];
  queue.push(root);
  while(queue.length > 0) {
    let current = queue.shift();
    console.log(current.val); //或者其他的操作
    if (current.left) {
      queue.push(current.left);
    }
    if (current.right) {
      queue.push(current.right);
    }
  }
}

中序遍历

左根右

递归

思路：递归左，根，递归右

1
2
3
4
5
6
7
8
function inorderTravelsal (root,array=[]) {
  if (root) {
    inorderTravelsal(root.left, array);
    array.push(root.val);
    inorderTravelsal(root.right, array);
  }
  return array;
}

非递归（迭代）

思路：
定义一个栈数组，一个结果数组

  1. 取根结点为目标节点，开始遍历
  2. 左孩子入栈，直到左孩子为空的节点
  3. 节点出栈，访问该节点
  4. 以右孩子为目标节点，依次执行前三项
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function inorderTravelsal2 (root) {
  let stack = [];
  let result = [];
  let current = root;
  while ( current || stack.length > 0 ) {
    while ( current ) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.val);
    current = current.right;
  }
  return result;
}
前序遍历

根左右

递归

思路：根，递归左，递归右

1
2
3
4
5
6
7
8
function preorderTravelsal(root,array=[]){
  if(root){
    array.push(root.val)
    preorderTravelsal(root.left,array)
    preorderTravelsal(root.right,array)
}
  return array
}

非递归（迭代）

思路：
定义一个栈数组，一个结果数组

  1. 取根结点为目标节点，开始遍历
  2. 访问目标节点
  3. 左孩子入栈，直到左孩子为空的节点
  4. 节点出栈，以右孩子为目标节点，依次执行前三项
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function preorderTravelsal2(root){
  let stack = []
  let result = []
  let current = root
  while(current || stack.length>0){
    while(current){
      result.push(current.val)
      stack.push(current)
      current = current.left
    }
    current = stack.pop()
    current = current.right
  }
  return result
}
后序遍历

左右根

递归

思路：递归左，递归右，根

1
2
3
4
5
6
7
8
function postorderTravelsal(root,array=[]){
  if(root){
    postorderTravelsal(root.left,array)
    postorderTravelsal(root.right,array)
    array.push(root.val)
  }
  return array
}

非递归（迭代）

思路：
定义一个栈数组，一个结果数组

  1. 取根结点为目标节点，开始遍历
  2. 用一个标志位last来标记上一个访问的节点
  3. 左孩子入栈，直到左孩子为空的节点
  4. 如果栈顶节点的右节点为空或者右节点被访问过=>节点出栈，访问该节点，将节点标记为已访问
  5. 否则，以右孩子为目标节点，重复以上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function postorderTravelsal2(root){
  let result = []
  let stack = []
  let current = root
  let last = null
  while(current || stack.length>0){
    while(current){
      stack.push(current)
      current = current.left
    }
    current = stack[stack.length-1]
    if(!current.right||current.right==last){
      current = stack.pop()
      result.push(current.val)
      last = current
      current = null
    }
    else{
      current = current.right
    }
  }
  return result
}

重建二叉树

根据前序遍历pre和中序遍历vin重建二叉树

思路：

  1. 如果长度是0或者1，直接return null或者return一个节点
  2. 前序遍历找到根节点root（第一个）
  3. 找到root在中序中的位置index
  4. 根据index得到左右子树的前、中遍历
  5. 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function reconstructBinaryTree(pre,vin){
  if(pre.length===0){
    return null
  }
  if(pre.length===1){
    return new TreeNode(pre[0])
  }
  const value = pre[0]
  const index = vin.indexOf(value)
  const preLeft = pre.slice(1,index+1)
  const preRight = pre.slice(index+1)
  const vinLeft = vin.slice(0,index)
  const vinRight = vin.slice(index+1)
  let node = new TreeNode(value)
  node.left = reconstructBinaryTree(preLeft,vinLeft)
  node.right = reconstructBinaryTree(preRight,vinRight)
  return node
}

对称二叉树

根节点相同，左右节点交换位置

判断是不是对称二叉树

思路：判断两个节点的关系

  1. 如果都没有，true
  2. 如果有一个没有，false
  3. 如果值不同，false
  4. 递归：比较节点1的左和节点2的右，比较节点1的右和节点2的左
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isSymmetrical(root){
  return isSymmetricalTree(root,root)
}
function isSymmetricalTree(node1,node2){
  if(!node1 && !node2){
    return true
  }
  if(!node1 || !node2){
    return false
  }
  if(node1.val!=node2.val){
    return false
  }
  return isSymmetricalTree(node1.left,node2.right) && isSymmetricalTree(node1.right,node2.left)
}
求对称二叉树
1
2
3
4
5
6
function invertTree(root){
  if(root){
    [root.left,root.right] = [invertTree(root.right),invertTree(root.left)];
  }
  return root
}

二叉搜索树

  • 左子树的所有节点都小于根节点的值
  • 右子树的所有节点都大于根节点的值
  • 左右子树分别为二叉搜索树
判断是不是二叉搜索树

思路：利用二叉搜索树的中序遍历是有序的特点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var isValidBST = function(root) {
    const queue = [];
    function dfs(root){
        if (!root){
            return;
        }
        root.left && dfs(root.left);
        queue.push(root.val);
        root.right && dfs(root.right);
    }
    dfs(root)
    for(let i=0; i<queue.length; i++){
        if(queue[i] >= queue[i+1]){
            return false;
        }
    }
    return true;
};
判断是不是一个二叉搜索树的后序遍历

思路：后序遍历 = 左子树 + 右子树 + 根

  1. 先检测左子树，左侧比根节点小的值都被判定为左子树
  2. 除最后一个节点外和左子树的其他值为右子树，右子树有一个比根节点小，则返回false
  3. 若存在左、右子树，递归检测左、右子树是否符合规范
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function verifySequenceOfBST(sequence){
  if(sequence && sequence.length > 0){
    let root = sequence[sequence.length-1]
    for(var i=0;i<sequence.length-1;i++){
      if(sequence[i]>root){
        break
      }
    }
    for(let j=i;j<sequence.length-1;j++){
      if(sequence[j]<root){
        return false
      }
    }
    let left = true
    if(i>0){
      left = verifySequenceOfBST(sequence.slice(0,i))
    }
    let right = true
    if(i<sequence.length-1){
      right = verifySequenceOfBST(sequence.slice(i,sequence.length-1))
    }
    return left && right
  }
}

二叉树的深度

深度：根节点到最远叶子节点的最长路径上的节点数

二叉树的最大深度
1
2
3
4
5
6
function maxDepth(root){
  if(root==null){
    return 0
  }
  return 1 + Math.max(maxDepth(root,left),maxDepth(root.right))
}
二叉树的最小深度
1
2
3
4
5
6
7
8
9
10
11
12
function minDepth(root){
  if(!root){
    return 0;
  }
  if(!root.left){
    return minDepth(root.right)+1;
  }
  if(!root.right){
    return minDepth(root.left)+1;
  }
  return 1 + Math.min(minDepth(root.left),minDepth(root.right));
}

平衡二叉树

  • 每个子树的深度之差不超过1
判断平衡二叉树

思路：

  1. 后序遍历二叉树，在遍历二叉树每个节点前都会遍历其左右子树
  2. 比较左右子树的深度，若差值大于1则返回一个标记-1，表示不平衡
  3. 左右子树有一个不平衡，或左右子树差值大于1，则整棵树不平衡
  4. 若左右子树平衡，返回当前树的深度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    function isBalanced(root){
      return depth(root)!=-1;
    }
    function depth(node){
      if(!node){
        return 0;
      }
      const left = depth(node.left);
      const right = depth(node.right);
      if(left==-1||right==-1||Math.abs(left-right)>1){
        return -1;
      }
      return Math.max(left,right)+1
    }

二叉树的层平均值

思路：

  1. 用层序遍历bfs的方法，维护一个队列去遍历节点
  2. 用for循环控制一层的节点逐个出列，节点值累加求和
  3. 节点出列的同时，下一层的子节点加入队列，在for循环结束时候，队列中就全是下一层的节点
  4. 用当前层的求个除以节点个数，加入结果数组
  5. 接着处理下一层，重复以上步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const averageOfLevels = (root) => {
  const res = [];
  const queue = [];
  queue.push(root);
  while (queue.length) {
    const levelSize = queue.length;
    let levelSum = 0;
    for(let i=0;i<levelSize;i++) {
      const cur = queue.shift();
      levelSum += cur.val;
      if(cur.left) {
        queue.push(cur.left);
      }
      if(cur.right) {
        queue.push(cur.right);
      }
    }
    res.push(levelSum / levelSize)
  }
  return res;
}