13.3 树与图算法
面试重要程度：⭐⭐⭐⭐⭐
常见提问方式： "手写二叉树遍历" "实现图的DFS/BFS" "二叉搜索树操作"
预计阅读时间：45分钟
🌳 二叉树基础结构
树节点定义
/**
* 二叉树节点定义
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* N叉树节点定义
*/
public class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int val) {
this.val = val;
}
public Node(int val, List<Node> children) {
this.val = val;
this.children = children;
}
}
🔄 二叉树遍历
递归遍历
/**
* 二叉树递归遍历
*/
public class BinaryTreeTraversalRecursive {
/**
* 前序遍历（根-左-右）
* LeetCode 144: Binary Tree Preorder Traversal
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorderHelper(root, result);
return result;
}
private void preorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return;
result.add(node.val); // 访问根节点
preorderHelper(node.left, result); // 遍历左子树
preorderHelper(node.right, result); // 遍历右子树
}
/**
* 中序遍历（左-根-右）
* LeetCode 94: Binary Tree Inorder Traversal
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return;
inorderHelper(node.left, result); // 遍历左子树
result.add(node.val); // 访问根节点
inorderHelper(node.right, result); // 遍历右子树
}
/**
* 后序遍历（左-右-根）
* LeetCode 145: Binary Tree Postorder Traversal
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return;
postorderHelper(node.left, result); // 遍历左子树
postorderHelper(node.right, result); // 遍历右子树
result.add(node.val); // 访问根节点
}
}
迭代遍历
/**
* 二叉树迭代遍历
*/
public class BinaryTreeTraversalIterative {
/**
* 前序遍历迭代实现
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
// 先压入右子树，再压入左子树（栈的特性）
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
/**
* 中序遍历迭代实现
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// 一直向左走到底
while (current != null) {
stack.push(current);
current = current.left;
}
// 处理栈顶元素
current = stack.pop();
result.add(current.val);
// 转向右子树
current = current.right;
}
return result;
}
/**
* 后序遍历迭代实现
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode lastVisited = null;
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
if (current != null) {
stack.push(current);
current = current.left;
} else {
TreeNode peekNode = stack.peek();
// 如果右子树存在且未被访问过
if (peekNode.right != null && lastVisited != peekNode.right) {
current = peekNode.right;
} else {
result.add(peekNode.val);
lastVisited = stack.pop();
}
}
}
return result;
}
/**
* 层序遍历（BFS）
* LeetCode 102: Binary Tree Level Order Traversal
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(currentLevel);
}
return result;
}
}
🔍 二叉搜索树操作
BST基础操作
/**
* 二叉搜索树操作
*/
public class BinarySearchTreeOperations {
/**
* 验证二叉搜索树
* LeetCode 98: Validate Binary Search Tree
*/
public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBSTHelper(TreeNode node, long minVal, long maxVal) {
if (node == null) return true;
if (node.val <= minVal || node.val >= maxVal) {
return false;
}
return isValidBSTHelper(node.left, minVal, node.val) &&
isValidBSTHelper(node.right, node.val, maxVal);
}
/**
* 二叉搜索树中的搜索
* LeetCode 700: Search in a Binary Search Tree
*/
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}
/**
* 二叉搜索树中的插入操作
* LeetCode 701: Insert into a Binary Search Tree
*/
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
/**
* 删除二叉搜索树中的节点
* LeetCode 450: Delete Node in a BST
*/
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 {
// 找到要删除的节点
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
// 节点有两个子节点，找到右子树的最小节点
TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
}
return root;
}
private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
/**
* 二叉搜索树的最近公共祖先
* LeetCode 235: Lowest Common Ancestor of a Binary Search Tree
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
// 如果p和q都在左子树
if (p.val <
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
Java面试圣经 文章被收录于专栏
Java面试圣经，带你练透java圣经
