二叉树

1. 基础概念

2. 二叉树的递归遍历

2.1 二叉树的前序遍历

描述

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

示例1：

txt


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

思路

前序遍历就是先处理当前节点，再处理左右子节点。

144 - 二叉树的前序遍历

javascript


// 递归
var preorderTraversal = function(root) {
  const res = [];
  front(root, res);
  return res;
};

var front = (node, res) => {
  if(node) {
    res.push(node.val);
    front(node.left, res);
    front(node.right, res);
  }
}

// 迭代：由于递归基于栈实现，因此可以显式得使用栈来实现遍历
var preorderTraversal = function(root) {
  const res = [];
  const satck = [];
  if(root != null) {
    satck.push(root)
  }
  let cur;
  while(satck.length) {
    cur = satck.pop()
    if(cur != null) {
      // 右左中，出栈就是中左右
      if(cur.right) satck.push(cur.right);
      if(cur.left) satck.push(cur.left);
      satck.push(cur);
      // 使用null标记前一元素已被处理，下一步可以直接加入结果
      satck.push(null);
    } else {
      cur = satck.pop();
      res.push(cur.val);
    }
  }
  return res;
};

2.2 二叉树的后序遍历

描述

LeetCode145 - 给你一棵二叉树的根节点 root，返回其节点值的后序遍历。简单

示例1：

txt


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

思路

后序遍历就是先处理左右两个子节点，再处理当前节点。

145 - 二叉树的后序遍历

javascript


// 递归
var postorderTraversal = function(root) {
  const res = [];
  backend(root, res);
  return res;
};

var backend = (node, res) => {
  if(node) {
    backend(node.left, res);
    backend(node.right, res);
    res.push(node.val);
  }
}

// 迭代
var postorderTraversal = function(root) {
  const res = [];
  const stack = [];
  if(root != null) stack.push(root);
  let cur;
  while(stack.length) {
    cur = stack.pop();
    if(cur != null) {
      stack.push(cur);
      stack.push(null);
      if(cur.right) stack.push(cur.right);
      if(cur.left) stack.push(cur.left);
    } else {
      cur = stack.pop();
      res.push(cur.val);
    }
  }  
  return res;
};

2.3 二叉树的中序遍历

描述

LeetCode94 - 给定一个二叉树的根节点 root，返回它的中序遍历。简单

示例1：

txt


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

思路

中序遍历就是先处理左子节点，再处理当前节点，最后是右子节点。

94 - 二叉树的中序遍历

javascript


// 递归
var inorderTraversal = function(root) {
  const res = [];
  inOrder(root, res);
  return res;
};

var inOrder = (node, res) => {
  if(node) {
    inOrder(node.left, res);
    res.push(node.val);
    inOrder(node.right, res);
  }
}

// 迭代
var inorderTraversal = function(root) {
  const res = [];
  const stack = [];
  if(root != null) stack.push(root);
  let cur;
  while(stack.length) {
    cur = stack.pop();
    if(cur != null) {
      if(cur.right) stack.push(cur.right);
      stack.push(cur);
      stack.push(null);
      if(cur.left) stack.push(cur.left);
    } else {
      cur = stack.pop();
      res.push(cur.val);
    }
  }
  return res;
};

2.4 N叉树的前序遍历

描述

LeetCode589 - 给定一个 n 叉树的根节点 root，返回其节点值的前序遍历。n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。简单

示例1：

txt


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

思路

递归：先遍历当前节点，再按顺序遍历子节点。

589 - N叉树的前序遍历

javascript


// 递归
var preorder = function(root) {
  const res = [];
  preorderNode(root, res);
  return res;
};

var preorderNode = function(node, res) {
  if(node) {
    res.push(node.val);
    node.children.forEach(item => {
      preorderNode(item, res);
    })
  }
}

// 迭代
var preorder = function(root) {
  const res = [];
  const stack = [];
  if(root) stack.push(root);
  let cur;
  while(stack.length) {
    cur = stack.pop();
    if(cur) {
      for(let i = cur.children.length - 1; i > -1; i--) {
        stack.push(cur.children[i]);
      }
      stack.push(cur);
      stack.push(null);
    } else {
      cur = stack.pop();
      res.push(cur.val);
    }
  }
  return res;
};

2.5 N叉树的后序遍历

描述

LeetCode590 - 给定一个 n 叉树的根节点 root，返回其节点值的后序遍历。n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。简单

示例1：

txt


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

思路

递归：先遍历孩子节点，再处理当前节点。

590 - N叉树的后序遍历

javascript


// 递归
var postorder = function(root) {
  const res = [];
  postOrderNode(root, res);
  return res;
};

var postOrderNode = function(node, res) {
  if(node) {
    node.children.forEach(item => {
      postOrderNode(item, res);
    })
    res.push(node.val);
  }
}

// 迭代
var postorder = function(root) {
  const res = [];
  const stack = [];
  if(root) stack.push(root);
  let cur;
  while(stack.length) {
    cur = stack.pop();
    if(cur) {
      stack.push(cur);
      stack.push(null);
      for(let i = cur.children.length - 1; i > -1; i--) {
        stack.push(cur.children[i]);
      }
    } else {
      cur = stack.pop();
      res.push(cur.val)
    }
  }
  return res;
};

3. 二叉树的层序遍历

3.1 二叉树的层序遍历

描述

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

示例1：

txt


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

示例2：

txt


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

思路

树的递归遍历，也就是深度优先搜索，可以使用栈实现；层序遍历，也就是广度优先搜索，可以使用队列实现。

102 - 二叉树的层序遍历

javascript


var Queue = function () {
  this.items = {};
  this.count = 0;
  this.lowestCount = 0;
}

Queue.prototype.enQueue = function (element) {
  this.items[this.count++] = element;
}

Queue.prototype.deQueue = function () {
  if (this.size() > 0) {
    const temp = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return temp;
  }
  return undefined;
}

Queue.prototype.size = function () {
  return this.count - this.lowestCount;
}

var levelOrder = function (root) {
  const queue = new Queue();
  const res = [];
  if (root) queue.enQueue(root);
  let cur, arr;
  while (queue.size() > 0) {
    // 本层的节点数
    let size = queue.size();
    arr = []
    for(let i = 0; i < size; i++) {
      cur = queue.deQueue();
      arr.push(cur.val);
      if (cur.left) queue.enQueue(cur.left);
      if (cur.right) queue.enQueue(cur.right);
    }
    res.push(arr);
    arr = [];
  }
  return res;
};

3.2 二叉树的层序遍历II

描述

LeetCode107 - 给你二叉树的根节点 root，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。中等

示例1：

txt


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

示例2：

txt


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

思路

使用广度优先搜索，再将结果反转就是自底向上的层序遍历结果。

107 - 二叉树的层序遍历II

javascript


var levelOrderBottom = function(root) {
  const queue = new Queue();
  const res = [];
  let cur, arr = [];
  if(root) queue.enQueue(root);
  while(queue.size() > 0) {
    let size = queue.size();
    for(let i = 0; i < size; i++) {
      cur = queue.deQueue();
      arr.push(cur.val);
      if(cur.left) queue.enQueue(cur.left);
      if(cur.right) queue.enQueue(cur.right);
    }
    res.push(arr);
    arr = [];
  }   
  let left = 0, right = res.length - 1, temp;
  while(left < right) {
    temp = res[right];
    res[right] = res[left];
    res[left] = temp;
    left++;
    right--;
  }
  return res;
};

3.3 二叉树的右视图

描述

LeetCode199 - 给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。中等

示例1：

txt


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

示例2：

txt


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

思路

层序遍历，将每层最后一个节点加入结果。

199 - 二叉树的右视图

javascript


var rightSideView = function(root) {
  const res = [];
  const queue = new Queue();
  if(root) queue.enQueue(root);
  let cur, size;
  while(queue.size() > 0) {
    size = queue.size();
    for(let i = 0; i < size; i++) {
      cur = queue.deQueue();
      // 将每层最后一个元素加入结果
      if(i === size - 1) {
        res.push(cur.val);
      }
      if(cur.left) queue.enQueue(cur.left);
      if(cur.right) queue.enQueue(cur.right);
    }
  }
  return res;
};

3.4 二叉树的层平均值

描述

LeetCode637 - 给定一个非空二叉树的根节点 root, 以数组的形式返回每一层节点的平均值。与实际答案相差 10^-5 以内的答案可以被接受。简单

示例1：

txt


输入：[3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]

思路

层序遍历，将每层的平均值加入结果。

637 - 二叉树的层平均值

javascript


var averageOfLevels = function(root) {
  const res = [];
  const queue = new Queue();
  let cur, sum, size;
  if(root) queue.enQueue(root);
  while(queue.size() > 0) {
    size = queue.size();
    sum = 0;
    for(let i = 0; i < size; i++) {
      cur = queue.deQueue();
      sum += cur.val;
      if(cur.left) queue.enQueue(cur.left);
      if(cur.right) queue.enQueue(cur.right);
    }
    res.push(sum / size);
  }
  return res;
};

3.5 N 叉树的层序遍历

描述

LeetCode429 - 给定一个 N 叉树，返回其节点值的层序遍历，即从左到右，逐层遍历。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。中等

示例1：

txt


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

思路

跟二叉树层序遍历类似，只不过处理左右子节点变成了处理全部子节点。

429 - N叉树的层序遍历

javascript


var levelOrder = function(root) {
  const res = [];
  const queue = new Queue();
  let cur, size, arr = [];
  if(root) queue.enQueue(root);
  while(queue.size() > 0) {
    size = queue.size();
    for(let i = 0; i < size; i++) {
      cur = queue.deQueue();
      arr.push(cur.val);
      cur.children.forEach(item => {
        queue.enQueue(item);
      })
    }
    res.push(arr);
    arr = [];
  }
  return res;
};

3.6 在每个树行中找最大值

描述

LeetCode515 - 给定一棵二叉树的根节点 root，请找出该二叉树中每一层的最大值。中等

示例1：

txt


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

示例2：

txt


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

思路

层序遍历，记录下每层中最大值并加入结果。

515 - 在每个树行中找最大值

javascript


var largestValues = function (root) {
  const res = [];
  const queue = new Queue();
  let cur, size, max = undefined;
  if (root) queue.enQueue(root);
  while (queue.size() > 0) {
    size = queue.size();
    for (let i = 0; i < size; i++) {
      cur = queue.deQueue();
      if (max === undefined || cur.val > max) {
        max = cur.val;
      }
      if (cur.left) queue.enQueue(cur.left);
      if (cur.right) queue.enQueue(cur.right);
    }
    res.push(max);
    max = undefined;
  }
  return res;
};

3.7 填充每个节点的下一个右侧节点指针

描述

LeetCode116 - 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：中等


struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例1：

txt


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

思路

层序遍历，将每层非最后一个节点的 next 指针指向下一节点，最后一个节点指向 null。为了便于操作，将每层从右到左遍历。

116 - 填充每个节点的下一个右侧节点指针

javascript


var connect = function(root) {
  const queue = new Queue();
  let cur, size, prev = null;
  if(root) queue.enQueue(root);
  while(queue.size() > 0) {
    size = queue.size();
    for(let i = 0; i < size; i++) {
      cur = queue.deQueue();
      cur.next = prev;
      prev = cur;
      if(cur.right) queue.enQueue(cur.right);
      if(cur.left) queue.enQueue(cur.left);
    } 
    prev = null;
  }
  return root;
};

3.8 填充每个节点的下一个右侧节点指针II

描述

LeetCode117 - 给定一个二叉树：中等


struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例1：

txt


输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]

思路

层序遍历，将每层非最后一个节点的 next 指针指向下一节点，最后一个节点指向 null。

117 - 填充每个节点的下一个右侧节点指针II

javascript


var connect = function (root) {
  const queue = new Queue();
  if (root) queue.enQueue(root);
  let cur, size, prev = null;
  while (queue.size() > 0) {
    size = queue.size();
    for (let i = 0; i < size; i++) {
      cur = queue.deQueue();
      cur.next = prev;
      prev = cur;
      if (cur.right) queue.enQueue(cur.right);
      if (cur.left) queue.enQueue(cur.left);
    }
    prev = null;
  }
  return root;
};

4. 翻转二叉树

描述

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

示例1：

txt


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

思路

使用递归将每个节点的左右子节点交换即可。

226 - 翻转二叉树

javascript


var invertTree = function(root) {
  if(root == null) {
    return null;
  }
  const temp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(temp);
  return root;
};

5. 对称二叉树

5.1 对称二叉树

描述

LeetCode101 - 给你一个二叉树的根节点 root，检查它是否轴对称。简单

示例1：

txt


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

思路

迭代：层序遍历+双指针。

递归：深度优先搜索，注意当前左右节点值相同时，结果由子节点决定。

101 - 对称二叉树

javascript


// 递归
var isSymmetric = function(root) {
  if(root == null) return true;
  return compare(root.left, root.right);
};

var compare = function(leftNode, rightNode) {
  if(leftNode == null && rightNode == null) {
    return true;
  } else if(leftNode == null && rightNode != null || leftNode != null && rightNode == null) {
    return false;
  } else if(leftNode.val !== rightNode.val) {
    return false;
  }
  return compare(leftNode.left, rightNode.right) && compare(leftNode.right, rightNode.left)
}

// 迭代
var isSymmetric = function (root) {
  const queue = new Queue();
  if(root == null) return true;
  queue.enQueue(root);
  let cur, left, right, arr = [], size;
  while (queue.size() > 0) {
    size = queue.size();
    for (let i = 0; i < size; i++) {
      cur = queue.deQueue();
      if (cur.left) queue.enQueue(cur.left);
      if (cur.right) queue.enQueue(cur.right);
      arr.push(cur);
    }
    left = 0;
    right = arr.length - 1;
    while (left <= right) {
      if (arr[left].left?.val !== arr[right].right?.val || arr[left].right?.val !== arr[right].left?.val) {
        return false;
      }
      left++;
      right--;
    }
    arr = [];
  }
  return true;
};

5.2 相同的树

描述

LeetCode100 - 给你两棵二叉树的根节点 p 和 q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。简单

示例1：

txt


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

思路

深度优先搜索，当前层节点值相同时，结果由子节点决定。

100 - 相同的树

javascript


var isSameTree = function(p, q) {
  return compare(p, q);
};

var compare = function(leftNode, rightNode) {
  if(leftNode == null && rightNode == null) {
    return true;
  } else if(leftNode == null && rightNode != null || leftNode != null && rightNode == null) {
    return false;
  } else if(leftNode.val !== rightNode.val) {
    return false;
  }
  return compare(leftNode.left, rightNode.left) && compare(rightNode.right, leftNode.right);
}

5.3 另一棵树的子树

描述

LeetCode572 - 给你两棵二叉树 root 和 subRoot。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true；否则，返回 false。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。简单

示例1：

txt


输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

思路

暴力：遍历 root 的每个节点，判断以该节点为根节点的树是否与 subRoot 相同。

kmp：两棵树以同一种方式递归遍历得到两个序列，判断 subRoot 的序列是否在 root 序列中。需要注意树的递归遍历序列不能唯一确定一棵树，需要将空的子节点用特殊标记表示并加入序列，比如左子节点为空，用字符串 lNull 表示，右子节点为空，用 rNull 表示，这样才能唯一确定一棵树。

572 - 另一棵树的子树

javascript


// 暴力：深度优先搜索
var isSubtree = function(root, subRoot) {
  if(root == null) return false;
  if(compare(root, subRoot)) {
    return true;
  }
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

var compare = function(leftNode, rightNode) {
  if(leftNode == null && rightNode == null) {
    return true;
  } else if(leftNode == null && rightNode != null || leftNode != null && rightNode == null) {
    return false;
  } else if(leftNode.val != rightNode.val) {
    return false;
  }
  return compare(leftNode.left, rightNode.left) && compare(leftNode.right, rightNode.right);
}

// kmp
var isSubtree = function(root, subRoot) {
  const rootArr = [];
  const subRootArr = [];
  preOrder(root, rootArr);
  preOrder(subRoot, subRootArr);

  let i = 0, j = 0;
  const next = getNext(subRootArr);
  while(i < rootArr.length && j < subRootArr.length) {
    if(rootArr[i] === subRootArr[j]) {
      i++;
      j++;
    } else {
      if(j == 0) {
        i++;
      } else {
        j = next[j - 1];
      }
    }
  }
  return j == subRootArr.length;
};

const preOrder = function(node, arr) {
  if(node) {
    arr.push(node.val);
    if(node.left) {
      preOrder(node.left, arr);
    } else {
      arr.push('lNull');
    }
    if(node.right) {
      preOrder(node.right, arr);
    } else {
      arr.push('rNull')
    }
  }
}

// 部分匹配表
const getNext = function(patternStr) {
  const next = [];
  next[0] = 0;

  let len = 0;
  let i = 1;
  while(i < patternStr.length) {
    if(patternStr[i] === patternStr[len]) {
      next[i] = ++len;
      i++;
    } else {
      if(len === 0) {
        next[i] = 0;
        i++;
      } else {
        len = next[len - 1];
      }
    }
  }
  return next;
}

6. 二叉树的最大深度

6.1 二叉树的最大深度

描述

LeetCode104 - 给定一个二叉树 root，返回其最大深度。简单

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例1：

txt


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

思路

深度优先搜索，对每个节点，返回左右子节点更大的深度加1。

104 - 二叉树的最大深度

javascript


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

6.2 N叉树的最大深度

描述

LeetCode559 - 给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。简单

示例1：

txt


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

思路

可以递归也可以层序遍历。

559 - N叉树的最大深度

javascript


var maxDepth = function(root) {
  if(root == null) {
    return 0;
  }
  let max = 0, cur;
  root.children.forEach(item => {
    cur = maxDepth(item);
    if(cur > max) max = cur;
  })
  return 1 + max;
};

7. 二叉树的最小深度

描述

LeetCode111 - 给定一个二叉树，找出其最小深度。简单

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例1：

txt


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

思路

与求二叉树最大深度类似，深度优先搜索，对每个节点，返回左右子节点更小的深度加1。

111 - 二叉树的最小深度

javascript


var minDepth = function(root) {
  if(root == null) return 0;
  else if(root.left == null && root.right == null) return 1;
  else if(root.left == null) {
    return 1 + minDepth(root.right);
  } else if(root.right == null) {
    return 1 + minDepth(root.left);
  } else {
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
  }
};

8. 完全二叉树的节点个数

描述

LeetCode222 - 给你一棵完全二叉树的根节点 root，求出该树的节点个数。完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2^h 个节点。简单

示例1：

txt


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

描述

递归遍历：后序遍历。

迭代遍历：层序遍历，统计节点总数。

222 - 完全二叉树的节点个数

javascript


var countNodes = function(root) {
  if(root == null) return 0;
  else if(root.left == null && root.right == null) return 1;
  return 1 + countNodes(root.left) + countNodes(root.right);
};

9. 平衡二叉树

描述

LeetCode110 - 给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树是指该树所有节点的左右子树的高度相差不超过 1。简单

示例1：

txt


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

思路

首先想到的是遍历每个节点，判断是否平衡，由于每个节点都计算左右子节点高度，最终时间复杂度 O(n^2)。

优化：在计算节点高度的时候可以判断该节点是否平衡，不平衡直接返回，最后仅需计算根节点的高度就可判断是否平衡，时间复杂度 O(n)。

110 - 平衡二叉树

javascript


var isBalanced = function(root) {
  return getHeight(root) > -2;
};

var getHeight = function(node) {
  if(node == null) {
    return -1;
  }
  const leftHeight = getHeight(node.left);
  const rightHeight = getHeight(node.right);
  if(leftHeight == -2 || rightHeight == -2 || Math.abs(leftHeight - rightHeight) > 1) {
    return -2;
  }
  return 1 + Math.max(leftHeight, rightHeight)
}

10. 二叉树的所有路径

描述

LeetCode257 - 给你一个二叉树的根节点 root，按任意顺序，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。简单

示例1：

txt


输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

思路

后序遍历即可。

257 - 二叉树的所有路径

javascript


var binaryTreePaths = function (root) {
  if (root == null) return [];
  const path = [];
  const leftPath = binaryTreePaths(root.left);
  const rightPath = binaryTreePaths(root.right);
  if (leftPath.length || rightPath.length) {
    leftPath.forEach(p => {
      path.push(root.val + '->' + p);
    })
    rightPath.forEach(p => {
      path.push(root.val + '->' + p);
    })
  } else {
    path.push(root.val.toString())
  }
  return path;
};

11. 左叶子之和

描述

LeetCode404 - 给定二叉树的根节点 root，返回所有左叶子之和。简单

示例1：

txt


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

思路

遍历每个节点，将左叶子节点加入数组，最后返回数组的和。

404 - 左叶子之和

javascript


var sumOfLeftLeaves = function(root) {
  const nums = [];
  preOrder(root, nums);
  return nums.reduce((pre, cur) => pre + cur, 0);
};

var preOrder = function(node, res) {
  if(node != null) {
    if(node.left != null) {
      if(node.left.left == null && node.left.right == null) {
        res.push(node.left.val);
      } else {
        preOrder(node.left, res);
      }
    }
    if(node.right !== null) {
      preOrder(node.right, res);
    }
  } 
}

12. 找树左下角的值

描述

LeetCode513 - 给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。中等

示例1：

txt


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

思路

使用层序遍历应该是比较容易想到的方法，递归遍历要难一点。

513 - 找树左下角的值

javascript


// 层序遍历 BFS
var findBottomLeftValue = function(root) {
  const queue = new Queue();
  queue.enQueue(root);
  const res = [];
  let cur, size, arr = [];
  while(queue.size() > 0) {
    size = queue.size();
    for(let i = 0; i < size; i++) {
      cur = queue.deQueue();
      arr.push(cur.val);
      if(cur.left) queue.enQueue(cur.left);
      if(cur.right) queue.enQueue(cur.right);
    }
    res.push(arr);
    arr = [];
  }
  return res[res.length - 1][0]
};

// 先序遍历 DFS
var findBottomLeftValue = function (root) {
  const preOrder = (node, depth) => {
    if (node != null) {
      if (node.left == null && node.right == null) {
        if (depth + 1 > maxDepth) {
          maxDepth = depth + 1;
          res = node.val;
        }
      }
      if (node.left) preOrder(node.left, depth + 1);
      if (node.right) preOrder(node.right, depth + 1);
    }
  }

  let res, maxDepth = 0;
  preOrder(root, 0);
  return res;
};

13. 路径总和

13.1 路径总和

描述

LeetCode112 - 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。如果存在，返回 true；否则，返回 false。叶子节点是指没有子节点的节点。简单

示例1：

txt


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

思路

后序遍历，如果不是叶子节点，处理左右子节点时将目标值减去当前节点的值，如果是叶子节点且目标值等于节点值，则表明当前路径和等于最初的目标值。

112 - 路径总和

javascript


var hasPathSum = function(root, targetSum) {
  if(root === null) return false;
  // 有子节点，继续深度优先搜索
  if(root.left != null || root.right !== null) {
    const leftRes = hasPathSum(root.left, targetSum - root.val);
    // 剪枝
    if(leftRes) return true;
    return hasPathSum(root.right, targetSum - root.val);
  } else {
    return root.val === targetSum;
  }
};

13.2 路径总和II

描述

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

示例1：

txt


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

思路

后序遍历。同样在递归时传入目标值与当前节点的差值，如果叶子节点等于目标值，则将叶子节点的值返回，否则返回空数组。

113 - 路径总和II

javascript


var pathSum = function(root, targetSum) {
  if(root == null) return [];
  const res = [];
  if(root.left != null || root.right != null) {
    const leftRes = pathSum(root.left, targetSum - root.val);
    const rightRes = pathSum(root.right, targetSum - root.val);
    leftRes.forEach(p => {
      p.unshift(root.val)
      res.push(p);
    })
    rightRes.forEach(p => {
      p.unshift(root.val)
      res.push(p);
    })
    return res;
  } else {
    return root.val == targetSum ? [[root.val]] : []
  }
};

14. 从中序与后序遍历构造二叉树

14.1 从中序与后序遍历序列构造二叉树

描述

LeetCode106 - 给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。中等

inorder 和 postorder 都由不同的值组成。

示例1：

txt


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

思路

后序遍历数组最后一个元素即是根节点，利用根节点可将中序遍历序列分隔为左右子节点的中序遍历序列，树的中序遍历序列长度与后序遍历长度相同，即可得出左右子节点的后序遍历序列，以此递归可构造二叉树。

106 - 从中序与后序遍历序列构造二叉树

javascript


var buildTree = function(inorder, postorder) {
  return buildTreeByIndex(inorder, 0, inorder.length, postorder, 0, postorder.length);
};

const buildTreeByIndex = function(inorder, inorderStart, inorderEnd, postorder, postorderStart, postorderEnd) {
  if(postorderStart == postorderEnd) return null;

  // 根节点
  const root = new TreeNode();
  root.val = postorder[postorderEnd - 1];

  // 中序数组分隔
  let splitIndex = inorderStart;
  for(; splitIndex < inorderEnd; splitIndex++) {
    if(inorder[splitIndex] == root.val) break;
  }

  // 中序数组索引
  let leftInorderStart = inorderStart, leftInorderEnd = splitIndex;
  let rightInorderStart = splitIndex + 1, rightInorderEnd = inorderEnd;

  // 后序数组索引
  let leftPostorderStart = postorderStart, leftPostorderEnd = postorderStart + splitIndex - inorderStart;
  let rightPostorderStart = leftPostorderEnd, rightPostorderEnd = postorderEnd - 1;

  root.left = buildTreeByIndex(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);
  root.right = buildTreeByIndex(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);

  return root;
}

14.2 从前序遍历与中序遍历序列构造二叉树

描述

LeetCode105 - 给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。中等

示例1：

txt


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

思路

前序遍历序列的第一个元素即是根节点，得到根节点后可以将中序遍历分隔得到左右子树的中序遍历序列，进而可以得到左右子树的前序遍历序列，递归即可构造一棵二叉树。

105 - 从前序遍历与中序遍历序列构造二叉树

javascript


var buildTree = function(preorder, inorder) {
    return buildTreeByIndex(preorder, 0, preorder.length, inorder, 0, inorder.length);
};

const buildTreeByIndex = function(preorder, preorderStart, preorderEnd, inorder, inorderStart, inorderEnd) {
    if(inorderStart == inorderEnd) return null;

    // 根节点
    const root = new TreeNode();
    root.val = preorder[preorderStart];

    // 分隔中序序列
    let spiltIndex = inorderStart;
    for(; spiltIndex < inorderEnd; spiltIndex++) {
        if(inorder[spiltIndex] == root.val) break;
    }

    // 左右子树的中序序列
    let leftInorderStart = inorderStart, leftInorderEnd = spiltIndex;
    let rightInorderStart = spiltIndex + 1, rightInorderEnd = inorderEnd;

    // 左右子树的前序序列
    let leftPreorderStart = preorderStart + 1, leftPreorderEnd = leftPreorderStart + spiltIndex - inorderStart;
    let rightPreorderStart = leftPreorderEnd, rightPreorderEnd = preorderEnd;

    root.left = buildTreeByIndex(preorder, leftPreorderStart, leftPreorderEnd, inorder, leftInorderStart, leftInorderEnd);
    root.right = buildTreeByIndex(preorder, rightPreorderStart, rightPreorderEnd, inorder, rightInorderStart, rightInorderEnd);

    return root;
}

15. 最大二叉树

描述

LeetCode654 - 给定一个不重复的整数数组 nums。最大二叉树可以用下面的算法从 nums 递归地构建：中等

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的子数组前缀上构建左子树。
递归地在最大值右边的子数组后缀上构建右子树。

返回 nums 构建的最大二叉树。

示例1：

txt


输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]

思路

按规则递归即可，每次找到当前序列的最大值，再分割左右子节点序列。

654 - 最大二叉树

javascript


var constructMaximumBinaryTree = function(nums) {
  return buildTree(nums, 0, nums.length - 1);
};

const buildTree = function(nums, start, end) {
  if(start > end) return null;

  // 找最大值索引
  let maxIndex = start;
  for(let i = start; i <= end; i++) {
    if(nums[i] > nums[maxIndex]) {
      maxIndex = i;
    }
  }

  const root = new TreeNode();
  root.val = nums[maxIndex];

  // 分割左右子树
  root.left = buildTree(nums, start, maxIndex - 1);
  root.right = buildTree(nums, maxIndex + 1, end);

  return root;
}

16. 合并二叉树

描述

LeetCode617 - 给你两棵二叉树： root1 和 root2。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。简单

返回合并后的二叉树。

示例1：

txt


输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

思路

深度优先搜索，按题意处理即可。

617 - 合并二叉树

javascript


var mergeTrees = function(root1, root2) {
  if(root1 == null && root2 == null) return null;

  const root = new TreeNode();
  if(root1 == null) {
    root.val = root2.val;
    root.left = mergeTrees(null, root2.left);
    root.right = mergeTrees(null, root2.right);
  } else if(root2 == null) {
    root.val = root1.val;
    root.left = mergeTrees(root1.left, null);
    root.right = mergeTrees(root1.right, null);
  } else {
    root.val = root1.val + root2.val;
    root.left = mergeTrees(root1.left, root2.left);
    root.right = mergeTrees(root1.right, root2.right);
  }

  return root;
};

17. 二叉搜索树中的搜索

描述

LeetCode700 - 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null。简单

示例1：

txt


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

思路

二叉搜索树中的查找类似于二分查找。

700 - 二叉搜索树中的搜索

javascript


var searchBST = function(root, val) {
  let cur = root;
  while(cur) {
    if(cur.val == val) {
      return cur;
    } else if(cur.val > val) {
      cur = cur.left;
    } else {
      cur = cur.right;
    }
  }
  return null;
};

18. 验证二叉搜索树

描述

LeetCode98 - 给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。中等

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例1：

txt


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

思路

需要注意有效的二叉搜索树的定义，左边子树所有节点需小于当前节点，右边子树所有节点需大于当前节点。根据定义可知中序遍历会得到一个有序的序列，因此中序遍历，与上一个节点比较即可。

98 - 验证二叉搜索树

javascript


var isValidBST = function (root) {
  let maxValue = -Infinity;

  const inorder = (node) => {
    if (node == null) return true;
    const left = inorder(node.left);
    if(node.val <= maxValue) return false;
    else maxValue = node.val;
    const right = inorder(node.right);
    return left && right;
  }

  return preorder(root);
};

19. 二叉搜索树的最小绝对差

描述

LeetCode530 - 给你一个二叉搜索树的根节点 root，返回树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。简单

示例1：

txt


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

思路

二叉搜索树中序遍历有序。只需要中序遍历，比较当前元素与上一个元素的差值就能找到最小的差值。

530 - 二叉搜索树的最小绝对差

javascript


var getMinimumDifference = function(root) {
  let minAbs = Infinity, prev = null;
  const findMinAbs = (node) => {
    if(node.left) findMinAbs(node.left);
    if(prev !== null) {
      const diff = Math.abs(prev - node.val)
      if(diff < minAbs) {
        minAbs = diff;
      }
    }
    prev = node.val;
    if(node.right) findMinAbs(node.right)
  }
  findMinAbs(root);
  return minAbs;
};

20. 二叉搜索树中的众数

描述

LeetCode501 - 给你一个含重复值的二叉搜索树（BST）的根节点 root，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。如果树中有不止一个众数，可以按任意顺序返回。简单

示例1：

txt


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

思路

中序遍历可以得到有序序列，再利用当前值和上一个值在有序序列中找众数。

501 - 二叉搜索树中的众数

javascript


var findMode = function (root) {
  let count = 0, prev = null, res = [], maxVal = 0;
  const inorder = (node) => {
    if (node.left) inorder(node.left);
    if(prev === null) {
      count = 1;
    } else if(node.val === prev) {
      count++;
    } else {
      count = 1;
    }
    prev = node.val;
    if(count === maxVal) {
      res.push(node.val)
    }
    if(count > maxVal) {
      maxVal = count;
      res = [node.val];
    } 
    if (node.right) inorder(node.right);
  }
  preorder(root);
  return res;
};

21. 二叉树的公共祖先

描述

LeetCode236 - 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。一个节点也可以是它自己的祖先。中等

示例1：

txt


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

思路

后序遍历。如果节点等于指定节点或 null，则返回该节点；如果左右子节点递归结果均不为空，则当前节点为最小公共祖先，返回当前节点；如果左节点空右节点不空，返回右节点，否则返回左节点的遍历结果。

236 - 二叉树的公共祖先

javascript


var lowestCommonAncestor = function(root, p, q) {
  if(root === p || root === q || root === null) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if(left && right) return root;
  if(left == null) return right;
  return left;
};

22. 二叉搜索树的公共祖先

描述

LeetCode235 - 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。一个节点也可以是它自己的祖先。中等

示例1：

txt


输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出：6

思路

由于是二叉搜索树，两个节点的公共祖先的值一定在两个节点的值之间，因此从根节点开始先序遍历，找到位于两个节点值之间的值即可。

235 - 二叉搜索树的公共祖先

javascript


var lowestCommonAncestor = function(root, p, q) {
  let res = null;
  if(p.val > q.val) [p, q] = [q, p]
  const  preorder = (node, p, q) => {
    if(res === null && node.val >= p.val && node.val <= q.val) {
      res = node;
    } 
    if(res && (node.val < p.val || node.val > q.val)) return;
    if(node.left) preorder(node.left, p, q);
    if(node.right) preorder(node.right, p, q)
  }
  preorder(root, p, q);
  return res;
};

23. 二叉搜索树中的插入操作

描述

LeetCode701 - 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证新值和原始二叉搜索树中的任意节点值都不同。

可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。中等

示例1：

txt


输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]

思路

二叉搜索树的插入，基础操作。

701 - 二叉搜索树的插入操作

javascript


var insertIntoBST = function(root, val) {
  if(root == null) {
    root = new TreeNode(val);
    return root;
  }
  if(root.val > val) {
    if(root.left == null) {
      root.left = new TreeNode(val);
    } else {
      root.left = insertIntoBST(root.left, val);
    }
  } else {
    if(root.right == null) {
      root.right = new TreeNode(val);
    } else {
      root.right = insertIntoBST(root.right, val);
    }
  }
  return root;
};

24. 删除二叉搜索树中的节点

描述

LeetCode450 - 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。中等

示例1：

txt


输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]

思路

二叉搜索树删除节点，基础操作。

450 - 删除二叉搜索树中的节点

javascript


var deleteNode = function (root, key) {
  if (root == null) return null;
  if (root.val > key) {
    root.left = deleteNode(root.left, key);
  } else if (root.val < key) {
    root.right = deleteNode(root.right, key);
  } else {
    if (root.left == null && root.right == null) {
      root = null;
    } else if (root.left == null || root.right == null) {
      if (root.right == null) {
        root = root.left;
      } else {
        root = root.right;
      }
    } else {
      const temp = minBSTNode(root.right);
      root.val = temp.val;
      root.right = deleteNode(root.right, temp.val);
    }
  }
  return root;
};

// 找最小
const minBSTNode = function (node) {
  if (node.left) return minBSTNode(node.left)
  else return node;
}

25. 修剪二叉搜索树

描述

LeetCode669 - 给你二叉搜索树的根节点 root，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high] 中。修剪树不应该改变保留在树中的元素的相对结构 (如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。中等

示例1：

txt


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

思路

后序遍历，如果节点不在范围内就删除该节点。也可以利用二叉搜索树的性质，如果当前节点小于范围，则左子树全小，可以直接返回右子树的裁剪结果，如果超出范围，则右子树全部超出，可以直接返回左子树的裁剪结果。

669 - 修剪二叉搜索树

javascript


// 后序遍历
var trimBST = function(root, low, high) {
  if(root.left) root.left = trimBST(root.left, low, high);
  if(root.right) root.right = trimBST(root.right, low, high);
  if(root.val < low || root.val > high) root = deleteNode(root, root.val);
  return root;
};

const deleteNode = function(node, key) {
  if(node == null) {
    return null;
  } else if(node.val > key) {
    node.left = deleteNode(node.left, key);
  } else if(node.val < key) {
    node.right = deleteNode(node.right, key);
  } else {
    if(node.left == null && node.right == null) {
      node = null;
    } else if(node.left == null || node.right == null) {
      if(node.right == null) {
        node = node.left;
      } else {
        node = node.right;
      }
    } else {
      const temp = minTreeNode(node.right);
      node.val = temp.val;
      node.right = deleteNode(node.right, temp.val);
    }
  }
  return node;
}

const minTreeNode = function(node) {
  if(node.left) return minTreeNode(node.left);
  else return node;
}

// 二叉树性质
var trimBST = function(root, low, high) {
  if(root == null) return null;
  if(root.val < low) return trimBST(root.right, low, high);
  if(root.val > high) return trimBST(root.left, low, high);
  root.left = trimBST(root.left, low, high)
  root.right = trimBST(root.right, low, high);
  return root;
};

26. 将有序数组转为二叉搜索树

描述

LeetCode108 - 给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。简单

示例1：

txt


输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]

思路

平衡二叉搜索树的中序遍历是一个有序数组，且根节点一定靠近数组中心，因此直接从数组中心位置获取值作为根节点，以此分割数组即可。

108 - 将有序数组转为二叉搜索树

javascript


var sortedArrayToBST = function(nums) {
  const root = getAVL(nums, 0, nums.length - 1);
  return root;
};

const getAVL = function(arr, start, end) {
  if(start > end) return null;
  // 中间节点作为根节点
  const index = Math.floor((start + end) / 2);
  const root = new TreeNode(arr[index]);
  root.left = getAVL(arr, start, index - 1);
  root.right = getAVL(arr, index + 1, end);
  return root;
}

27. 将二叉搜索树转为累加树

描述

LeetCode538 - 给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。中等

示例1：

txt


输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

思路

二叉搜索树中序遍历有序，因此可以逆序中序遍历，则遍历过的节点都比当前节点值大，将当前节点值赋值遍历过节点的值总和就行。

538 - 把二叉搜索树转换为累加树

javascript


var convertBST = function(root) {
  let sum = 0;

  const inorder = (node) => {
    if(node == null) return;
    if(node.right) inorder(node.right);
    sum += node.val;
    node.val = sum;
    if(node.left) inorder(node.left);
  }

  inorder(root);
  return root;
};

二叉树 ​

1. 基础概念 ​

2. 二叉树的递归遍历 ​

2.1 二叉树的前序遍历 ​

2.2 二叉树的后序遍历 ​

2.3 二叉树的中序遍历 ​

2.4 N叉树的前序遍历 ​

2.5 N叉树的后序遍历 ​

3. 二叉树的层序遍历 ​

3.1 二叉树的层序遍历 ​

3.2 二叉树的层序遍历II ​

3.3 二叉树的右视图 ​

3.4 二叉树的层平均值 ​

3.5 N 叉树的层序遍历 ​

3.6 在每个树行中找最大值 ​

3.7 填充每个节点的下一个右侧节点指针 ​

3.8 填充每个节点的下一个右侧节点指针II ​

4. 翻转二叉树 ​

5. 对称二叉树 ​

5.1 对称二叉树 ​

5.2 相同的树 ​

5.3 另一棵树的子树 ​

6. 二叉树的最大深度 ​

6.1 二叉树的最大深度 ​

6.2 N叉树的最大深度 ​

7. 二叉树的最小深度 ​

8. 完全二叉树的节点个数 ​

9. 平衡二叉树 ​

10. 二叉树的所有路径 ​

11. 左叶子之和 ​

12. 找树左下角的值 ​

13. 路径总和 ​

13.1 路径总和 ​

13.2 路径总和II ​

14. 从中序与后序遍历构造二叉树 ​

14.1 从中序与后序遍历序列构造二叉树 ​

14.2 从前序遍历与中序遍历序列构造二叉树 ​

15. 最大二叉树 ​

16. 合并二叉树 ​

17. 二叉搜索树中的搜索 ​

18. 验证二叉搜索树 ​

19. 二叉搜索树的最小绝对差 ​

20. 二叉搜索树中的众数 ​

21. 二叉树的公共祖先 ​

22. 二叉搜索树的公共祖先 ​

23. 二叉搜索树中的插入操作 ​

24. 删除二叉搜索树中的节点 ​

25. 修剪二叉搜索树 ​

26. 将有序数组转为二叉搜索树 ​

27. 将二叉搜索树转为累加树 ​

二叉树

1. 基础概念

2. 二叉树的递归遍历

2.1 二叉树的前序遍历

2.2 二叉树的后序遍历

2.3 二叉树的中序遍历

2.4 N叉树的前序遍历

2.5 N叉树的后序遍历

3. 二叉树的层序遍历

3.1 二叉树的层序遍历

3.2 二叉树的层序遍历II

3.3 二叉树的右视图

3.4 二叉树的层平均值

3.5 N 叉树的层序遍历

3.6 在每个树行中找最大值

3.7 填充每个节点的下一个右侧节点指针

3.8 填充每个节点的下一个右侧节点指针II

4. 翻转二叉树

5. 对称二叉树

5.1 对称二叉树

5.2 相同的树

5.3 另一棵树的子树

6. 二叉树的最大深度

6.1 二叉树的最大深度

6.2 N叉树的最大深度

7. 二叉树的最小深度

8. 完全二叉树的节点个数

9. 平衡二叉树

10. 二叉树的所有路径

11. 左叶子之和

12. 找树左下角的值

13. 路径总和

13.1 路径总和

13.2 路径总和II

14. 从中序与后序遍历构造二叉树

14.1 从中序与后序遍历序列构造二叉树

14.2 从前序遍历与中序遍历序列构造二叉树

15. 最大二叉树

16. 合并二叉树

17. 二叉搜索树中的搜索

18. 验证二叉搜索树

19. 二叉搜索树的最小绝对差

20. 二叉搜索树中的众数

21. 二叉树的公共祖先

22. 二叉搜索树的公共祖先

23. 二叉搜索树中的插入操作

24. 删除二叉搜索树中的节点

25. 修剪二叉搜索树

26. 将有序数组转为二叉搜索树

27. 将二叉搜索树转为累加树