二叉树算法题解集
二叉树节点计数
给定一棵完全二叉树的根节点，计算该树中节点的总数。
方法一：广度优先搜索
通过层次遍历方式，在访问节点过程中计数。
public int countNodes(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int nodeCount = 0;
while (!queue.isEmpty()) {
nodeCount++;
TreeNode currentNode = queue.poll();
if (currentNode.left != null) queue.offer(currentNode.left);
if (currentNode.right != null) queue.offer(currentNode.right);
}
return nodeCount;
}
方法二：递归法
递归思路：树的节点数等于左子树节点数加右子树节点数加1，递归终止条件是节点为空。
简化递归实现：
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
详细递归实现：
class Solution {
public int countNodes(TreeNode root) {
return calculateNodeCount(root);
}
/**
* 计算指定节点所在子树的节点总数
* @param node 当前节点
* @return 子树节点总数
*/
public int calculateNodeCount(TreeNode node) {
if (node == null) return 0;
int leftCount = calculateNodeCount(node.left);
int rightCount = calculateNodeCount(node.right);
return leftCount + rightCount + 1;
}
}
方法三：优化递归法
利用完全二叉树的特性优化：
- 左右子树都是满二叉树，此时节点数为2^h-1
- 左子树为满二叉树，右子树为普通完全二叉树
- 左右子树都不是满二叉树
代码实现：
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
TreeNode leftChild = root.left;
TreeNode rightChild = root.right;
int leftDepth = 0, rightDepth = 0;
while (leftChild != null) {
leftDepth++;
leftChild = leftChild.left;
}
while (rightChild != null) {
rightDepth++;
rightChild = rightChild.right;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
平衡二叉树判断
判断给定的二叉树是否为平衡二叉树。
解题思路：递归获取左右子树的高度，当发现不平衡时，返回-1标识非平衡状态。
class Solution {
public boolean isBalanced(TreeNode root) {
return getTreeHeight(root) != -1;
}
int getTreeHeight(TreeNode node) {
if (node == null) return 0;
int leftHeight = getTreeHeight(node.left);
int rightHeight = getTreeHeight(node.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1){
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
}
二叉树路径问题
从根到叶的所有路径
给定二叉树的根节点，返回所有从根节点到叶子节点的路径。
方法一：递归回溯
List<String> pathResults = new ArrayList<>();
List<String> currentPath = new ArrayList<>();
public List<String> getAllPaths(TreeNode root) {
collectPaths(root);
return pathResults;
}
void collectPaths(TreeNode node) {
if (node.left == null && node.right == null) {
currentPath.add(node.val + "");
addPathToList(currentPath);
currentPath.remove(currentPath.size() - 1);
return;
}
currentPath.add(node.val + "->");
if (node.left != null) collectPaths(node.left);
if (node.right != null) collectPaths(node.right);
currentPath.remove(currentPath.size() - 1);
}
public void addPathToList(List path) {
String pathStr = "";
for (int i = 0; i < path.size(); i++) {
pathStr += path.get(i);
}
pathResults.add(pathStr);
}
方法二：迭代法
class Solution {
public List<String> getAllPaths(TreeNode root) {
Stack<Object> stack = new Stack<>();
List<String> results = new ArrayList<>();
if (root != null) {
stack.push(root);
stack.push(root.val + "");
}
while (!stack.isEmpty()) {
String currentPath = (String) stack.pop();
TreeNode currentNode = (TreeNode) stack.pop();
if (currentNode.left == null && currentNode.right == null) {
results.add(currentPath);
}
if (currentNode.right != null) {
stack.push(currentNode.right);
stack.push(currentPath + "->" + currentNode.right.val);
}
if (currentNode.left != null) {
stack.push(currentNode.left);
stack.push(currentPath + "->" + currentNode.left.val);
}
}
return results;
}
}
路径总和问题
判断是否存在路径总和等于目标值
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
}
}
找出所有路径总和等于目标值的路径
class Solution {
public List<List<Integer>> findAllPaths(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
if (root == null) return allPaths;
List<Integer> currentPath = new LinkedList<>();
currentPath.add(root.val);
searchPaths(root, targetSum - root.val, allPaths, currentPath);
return allPaths;
}
public void searchPaths(TreeNode node, int remainingSum,
List<List<Integer>> allPaths, List<Integer> currentPath) {
if (node.left == null && node.right == null && remainingSum == 0) {
allPaths.add(new ArrayList<>(currentPath));
}
if (node.left != null) {
currentPath.add(node.left.val);
searchPaths(node.left, remainingSum - node.left.val, allPaths, currentPath);
currentPath.remove(currentPath.size() - 1);
}
if (node.right != null) {
currentPath.add(node.right.val);
searchPaths(node.right, remainingSum - node.right.val, allPaths, currentPath);
currentPath.remove(currentPath.size() - 1);
}
}
}
左叶子节点求和
class Solution {
public int sumLeftLeaves(TreeNode root) {
if (root == null) return 0;
int leftValue = sumLeftLeaves(root.left);
if (root.left != null && root.left.left == null && root.left.right == null) {
leftValue = root.left.val;
}
int rightValue = sumLeftLeaves(root.right);
return leftValue + rightValue;
}
}
找树左下角的值
class Solution {
int maxDepth = -1;
int leftmostValue;
public int findBottomLeftValue(TreeNode root) {
findValue(root, 1);
return leftmostValue;
}
void findValue(TreeNode node, int depth) {
if (node.left == null && node.right == null) {
if (depth > maxDepth) {
maxDepth = depth;
leftmostValue = node.val;
}
return;
}
if (node.left != null) {
findValue(node.left, depth + 1);
}
if (node.right != null) {
findValue(node.right, depth + 1);
}
}
}
二叉树构造问题
从中序和后序遍历构造二叉树
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder.length == 0) return null;
int rootValue = postorder[postorder.length - 1];
TreeNode root = new TreeNode(rootValue);
if (postorder.length == 1) return root;
int rootIndex = 0;
for (; rootIndex < inorder.length; rootIndex++) {
if (inorder[rootIndex] == rootValue) break;
}
int[] leftInorder = Arrays.copyOfRange(inorder, 0, rootIndex);
int[] rightInorder = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);
int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
int[] rightPostorder = Arrays.copyOfRange(postorder, leftInorder.length, postorder.length - 1);
root.left = buildTree(leftInorder, leftPostorder);
root.right = buildTree(rightInorder, rightPostorder);
return root;
}
}
从前序和中序遍历构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) return null;
int rootValue = preorder[0];
TreeNode root = new TreeNode(rootValue);
if (preorder.length == 1) return root;
int rootIndex = 0;
for (; rootIndex < inorder.length; rootIndex++) {
if (inorder[rootIndex] == rootValue) break;
}
int[] leftInorder = Arrays.copyOfRange(inorder, 0, rootIndex);
int[] rightInorder = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);
int[] leftPreorder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
int[] rightPreorder = Arrays.copyOfRange(preorder, leftInorder.length + 1, preorder.length);
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
return root;
}
}
构建最大二叉树
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return buildMaxTree(nums, 0, nums.length - 1);
}
public TreeNode buildMaxTree(int[] nums, int left, int right) {
if (left > right) return null;
if (left == right) return new TreeNode(nums[left]);
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}
TreeNode root = new TreeNode(nums[maxIndex]);
root.left = buildMaxTree(nums, left, maxIndex - 1);
root.right = buildMaxTree(nums, maxIndex + 1, right);
return root;
}
}
合并二叉树
class Solution {
public TreeNode mergeTrees(TreeNode tree1, TreeNode tree2) {
if (tree1 == null) return tree2;
if (tree2 == null) return tree1;
tree1.val += tree2.val;
tree1.left = mergeTrees(tree1.left, tree2.left);
tree1.right = mergeTrees(tree1.right, tree2.right);
return tree1;
}
}
二叉搜索树问题
搜索二叉搜索树
class Solution {
public TreeNode search(TreeNode root, int target) {
if (root == null) return null;
while (root != null) {
if (root.val == target) return root;
else if (root.val > target) root = root.left;
else root = root.right;
}
return null;
}
}
验证二叉搜索树
class Solution {
public boolean isValid(TreeNode root) {
return validate(root, null, null);
}
public boolean validate(TreeNode node, Integer min, Integer max) {
if (node == null) return true;
if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
return false;
}
return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}
}
