节点定义
Java
public class TreeNode {
// 都有默认的零值
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {}
public TreeNode(int val) { this.val = val; }
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}function TreeNode(val) {
this.val = val;
this.left = null;
this.right = null;
}遍历方式
深度优先遍历
- 前序遍历（迭代：Stack + while 先右后左入栈）
- 中序遍历（迭代：Stack + 沿左深入栈，左空右替换）
- 后序遍历（迭代：同前序，但先左后右入栈，最后反转序列）（迭代：Stack + prev，左完，看 prev 是否为中右，是则中右入栈，否则中出栈访问）
前序遍历 - 迭代法
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if (root == null) return res;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
// 前序遍历的迭代法不让 null 入栈
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return res;
}中序遍历 - 迭代法
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
// 其实直接用 root 遍历也行
TreeNode curr = root;
while (curr != null || !st.isEmpty()) {
if (curr != null) {
// 中序遍历的迭代法也不让 null 入栈
st.push(curr);
curr = curr.left;
} else {
TreeNode top = st.pop();
res.add(top.val);
if (top.right != null) {
curr = top.right;
}
}
}
return res;
}
}后序遍历 - 迭代法
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root == null) return res;
// 当前遍历的节点
TreeNode curr = root;
// 上次遍历的节点
TreeNode prev = null;
while (curr != null || !st.isEmpty()) {
if (curr != null) {
// 一路向左，不为空则进栈
// 后序遍历也不让 null 入栈
st.push(curr);
curr = curr.left;
} else {
// 左到头了，看看栈顶
TreeNode top = st.peek();
// 栈顶元素有右孩子
if (top.right != null) {
// 如果右孩子不是上次访问的节点
if (top.right != prev) {
// 则以右孩子做为新子树的根，继续遍历
curr = top.right;
} else {
// 如果右孩子是上次访问的节点，说明该访问栈顶元素了
res.add(top.val);
st.pop();
// 记录 prev
prev = top;
}
} else {
// 栈顶元素没有右孩子，则直接访问栈顶元素
res.add(top.val);
st.pop();
// 记录 prev
prev = top;
}
}
}
return res;
}广度优先遍历
- 层序遍历（迭代：Queue + 按个遍历、用 size 按层遍历）
二叉树的属性
高度和深度
后序求高度，前序求深度。
对于节点来说，高度是从该节点到叶子节点的最大路径长度，深度是从根节点到该节点的路径长度。
对于二叉树来说，高度和深度是一样的，高度从根节点算起。
所以对于 104.二叉树的最大深度 和 111.二叉树的最小深度 要使用后序遍历，先处理左右子树的深度。
// 求最大深度
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int ld = maxDepth(root.left);
int rd = maxDepth(root.right);
return Math.max(ld, rd) + 1;
}
}
// 求最小深度
public int minDepth(TreeNode root) {
if (root == null) return 0;
int ld = minDepth(root.left);
int rd = minDepth(root.right);
// 如果当前节点左孩子为空，右孩子不为空，那么当前节点的最小深度就是右子树的最小深度 +1
if (root.left == null && root.right != null) {
return 1 + rd;
}
// 如果当前节点右孩子为空，左孩子不为空，那么当前节点的最小深度就是左子树的最小深度 +1
if (root.left != null && root.right == null) {
return 1 + ld;
}
// 如果左右孩子都不为空，则就取左右子树最小深度的较小者 +1
return Math.min(ld, rd) + 1;
}求节点数量
后序遍历，返回左右子树的节点数量之和 +1。
是否平衡
后序遍历，看左右子树的高度差是否小于等于 1。下面有个技巧，函数既能返回高度，也能返回是否是平衡二叉树的标志，不是则及时返回，不再深入递归下去。
public boolean isBalanced(TreeNode root) {
// 不等于 -1，说明是平衡的
return getHeightX(root) != -1;
}
public int getHeightX(TreeNode root) {
if (root == null) return 0;
int lh = getHeightX(root.left);
// 有一个子树不平衡，则整个树都不是平衡二叉树，用 -1 标志，及时返回
if (lh == -1) return -1;
int rh = getHeightX(root.right);
// 有一个子树不平衡，则整个树都不是平衡二叉树，用 -1 标志，及时返回
if (rh == -1) return -1;
// 高度差大于 1，则不是平衡二叉树
if (Math.abs(lh - rh) > 1) return -1;
return Math.max(lh, rh) + 1;
}找所有路径
前序，涉及到回溯的知识。先修改相关标志，再递归处理，然后再撤回相关标志的修改。
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new LinkedList<>();
helper(root, "", res);
return res;
}
public void helper(TreeNode root, String path, List<String> res) {
if (root == null) return;
// 进来就是访问，先拼接访问路径
path += root.val;
// 到达叶子节点，放入结果集
if (root.left == null && root.right == null) {
res.add(path);
return;
}
// 否则继续深入遍历，这里的 path + "->" 就是深入
// 而深入递归完，path 没变，就是回溯
helper(root.left, path + "->", res);
helper(root.right, path + "->", res);
}路经总和
和遍历顺序无关，涉及到了回溯，找到答案立即返回即可。
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null && root.val == targetSum) return true;
if (hasPathSum(root.left, targetSum - root.val)) return true;
if (hasPathSum(root.right, targetSum - root.val)) return true;
return false;
}二叉树的修改与构造
反转二叉树
前序、后序遍历，交换节点即可。
构造二叉树
前序 + 中序、后序 + 中序。核心思路就是根据前序或者后序找到根节点在中序中的位置，然后划分区间，递归构造。
构造最大的二叉树
指定一个序列（非前中后序序列），要求构造二叉树。一般采用前序遍历的方式，然后递归构造左右子树。
这里区间内最大值的查找采用了一次遍历的方式。
合并二叉树
这里开始同时遍历两棵树，即函数中传递两棵树的节点，采用一致的顺序遍历。
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
// root1、root2 都不为空，这里原地修改 root1，root2 也行，不用创建新节点
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}二叉搜索树的属性
二叉搜索树要记住的关键词：有序、中序、左边小于中间，中间小于右边、划区间（选方向）深入、双指针。
二叉搜索树中的搜索
// 迭代法
public TreeNode searchBST(TreeNode root, int val) {
// 划区间，选方向深入
// 直接修改 root 即可
while (root != null) {
if (val < root.val) {
root = root.left;
} else if (val > root.val) {
root = root.right;
} else {
return root;
}
}
return null;
}是否为二叉搜索树
中序遍历，双指针技巧，记住上一个遍历的节点。根据二叉搜索树的有序性，中序遍历中上一个节点的值一定比当前节点的值小。
// 记录上一个遍历的节点
private TreeNode prev;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
// 左子树是不是 BST，不是就返回 false
boolean lb = isValidBST(root.left);
if (!lb) return false;
// 上个节点的值是否大于当前节点，是则失序，返回 false
if (prev != null && prev.val >= root.val) return false;
// root 作为 prev，开始遍历右子树
prev = root;
// 右子树是不是 BST，不是就返回 false
boolean rb = isValidBST(root.right);
if (!rb) return false;
return true;
}二叉搜索树的最小绝对差
还是借助有序性（中序），最小的差一定在相邻节点之间。
private int min = Integer.MAX_VALUE;
private TreeNode prev;
public int getMinimumDifference(TreeNode root) {
traversal(root);
return min;
}
public void traversal(TreeNode root) {
if (root == null) return;
getMinimumDifference(root.left);
if (prev != null) {
int diff = root.val - prev.val;
if (diff < min) {
min = diff;
}
}
prev = root;
getMinimumDifference(root.right);
}二叉搜索树的众数
出现次数最多的树，众数可能有多个，一般思路是拿 Map 记录节点出现的次数，两次遍历，一次是找最大值，一次是将和最大值相等的节点记录在案。但这样的方法对什么树都有效，白瞎了二叉搜索树的特性。
// 记录最大次数
private int maxCount;
// 记录当前次数，每个节点都可使用
private int count;
// 记录上一个节点
private TreeNode prev;
// 存储结果
private List<Integer> list;
public int[] findMode(TreeNode root) {
maxCount = Integer.MIN_VALUE;
count = 0;
prev = null;
list = new LinkedList<>();
traversal(root);
// 将结果放入数组
int[] res = new int[list.size()];
int i = 0;
for (int e: list) {
res[i++] = e;
}
return res;
}
public void traversal(TreeNode root) {
if (root == null) return;
traversal(root.left);
if (prev == null) {
// 第一个节点，频率记为 1
count = 1;
} else if (prev.val == root.val) {
// 重复的节点，频率 +1
count++;
} else {
// 新节点，频率重置为 1（多个节点公用 count 的关键）
count = 1;
}
// 和当前最大频率相等，放进预结果列表
if (count == maxCount) {
list.add(root.val);
}
// 频率更大，更新 maxCount，
// 之前的预结果列表作废，因为有了频率更大的，并将最新的大频率值放进预结果列表
if (count > maxCount) {
maxCount = count;
list.clear();
list.add(root.val);
}
prev = root;
traversal(root.right);
}二叉搜索树转成累加树
借助有序性（右边比中间大），逆中序遍历。
private int prevVal;
public TreeNode convertBST(TreeNode root) {
if (root == null) return null;
// 先遍历右子树
convertBST(root.right);
// 将上一个节点的值加上
root.val += prevVal;
// 当前节点变为 prev
prevVal = root.val;
// 开始遍历左子树
convertBST(root.left);
return root;
}二叉搜索树的修改与构造
插入
插入节点都是作为叶子节点，借助有序性，选择正确的方向深入下去，找到叶子节点并插在下面。
// 递归法
public TreeNode insertIntoBST(TreeNode root, int val) {
// 往空树插入节点
if (root == null) return new TreeNode(val);
if (val < root.val) {
if (root.left != null) {
// 如果有左子树，则继续递归
root.left = insertIntoBST(root.left, val);
} else {
// 否则作为左子树
root.left = new TreeNode(val);
}
} else if (val > root.val) {
if (root.right != null) {
// 如果有右子树，则继续递归
root.right = insertIntoBST(root.right, val);
} else {
// 否则作为右子树
root.right = new TreeNode(val);
}
}
return root;
}
// 迭代法
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
// 记录父节点
TreeNode parent = null;
TreeNode curr = root;
while (curr != null) {
// 每次遍历更新父节点
parent = curr;
if (curr.val < val) {
curr = curr.right;
} else {
curr = curr.left;
}
}
// 挂载节点
if (val < parent.val) {
parent.left = new TreeNode(val);
} else {
parent.right = new TreeNode(val);
}
return root;
}删除
else 里的代码值得反复观看。写代码前先探讨可能的情况，不要一股脑的就进行递归。
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// root 就是待删除的节点
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 左右均不为空，则寻找左子树中的最大值
TreeNode curr = root.left;
while (curr.right != null) {
curr = curr.right;
}
// 将待删除节点的右子树接到最大值节点的右子树上
curr.right = root.right;
// 既然 root.right 已经没了，那么新 root 就是老 root 的左子树
root = root.left;
}
return root;
}修剪
借助二叉搜索树的有序性，如果当前节点的值小于下界，则当前节点及其左子树都不用考虑，如果当前节点的值大于上界，则当前节点及其右子树都不用考虑。
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return null;
// root 不在区间内，直接返回，换根
if (root.val < low) {
return trimBST(root.right, low, high);
} else if (root.val > high) {
return trimBST(root.left, low, high);
}
// root 在区间内，保留，查看左右子树
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}构造
根据有序的节点序列，构造二叉搜索树，要求平衡。从数组中间开始（保证平衡），选节点作为根节点，然后两边递归构造。
public TreeNode sortedArrayToBST(int[] nums) {
return traversal(nums, 0, nums.length - 1);
}
public TreeNode traversal(int[] nums, int l, int r) {
if (l > r) return null;
// 优化，如果 l、r 相等，则直接生成节点并返回，不用再往下递归了
if (l == r) return new TreeNode(nums[l]);
int mid = (l + r) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = traversal(nums, l, mid - 1);
node.right = traversal(nums, mid + 1, r);
return node;
}二叉树公共祖先问题
左子树出现目标值，右子树出现目标值，则 root 就是最近公共祖先。
借助有序性，root 在区间内，root 就是最近公共祖先。
代码碎片
求节点的高度
// 后序遍历
int getHeight(TreeNode node) {
if (node == null) return 0;
int lh = getHeight(node.left);
int rh = getHeight(node.right);
return Integer.max(lh, rh) + 1;
}求平衡二叉树的高度，如果不是平衡二叉树，则返回 -1
// 后序遍历
int getHeight(TreeNode node) {
if (root == null) return 0;
int lh = getHeight(node.left);
if (lh == -1) return -1;
int rh = getHeight(node.right);
if (rh == -1) return -1;
if (Math.abs(lh - rh) > 1) return -1;
return Integer.max(lh, rh) + 1;
}层序遍历
void layer(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
// 处理当前 node
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
}上面的方法每次循环只处理一个节点，下面的方法每次循环处理一层的节点。
void layer(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
// size 就是当前层的节点数
int size = q.size();
// 一次处理一层
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
// 处理 node
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
}
}