力扣hot100第五天

二叉树 94.二叉树的中序遍历 题目

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

代码

class Solution { List ans = new ArrayList<>();

public List<Integer> inorderTraversal(TreeNode root) { if (root != null) { inorderTraversal(root.left); ans.add(root.val); inorderTraversal(root.right); } return ans; }

}

前序遍历

class Solution { List ans = new ArrayList<>();

public List<Integer> preorderTraversal(TreeNode root) { if (root == null) return new ArrayList<>(); ans.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return ans; }

}

后序遍历

class Solution { List ans = new ArrayList<>();

public List<Integer> postorderTraversal(TreeNode root) { if (root == null) return new ArrayList<>(); postorderTraversal(root.left); postorderTraversal(root.right); ans.add(root.val); return ans; }

}

104.二叉树的最大深度 题目

给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

代码

class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } }

226.翻转二叉树 题目

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

代码

class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return root; TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.right = left; root.left = right; return root; } }

101.对称二叉树 题目

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

代码

class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) return true; return isSymmetric(root.left, root.right); }

public boolean isSymmetric(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; if (left.val != right.val) return false; return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left); }

}

543.二叉树的直径 题目

给你一棵二叉树的根节点，返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。

代码

class Solution { int ans = 0;

public int diameterOfBinaryTree(TreeNode root) { if (root == null) return 0; depth(root); return ans; } public int depth(TreeNode root) { if (root == null) return 0; int left = depth(root.left); int right = depth(root.right); ans = Math.max(ans, left + right); return 1 + Math.max(left, right); }

}

102.二叉树的层序遍历 题目

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

代码

class Solution { public List<List> levelOrder(TreeNode root) { if (root == null) return new ArrayList<>(); Queue queue = new LinkedList<>(); List<List> ans = new ArrayList<>(); queue.offer(root); while (!queue.isEmpty()) { int n = queue.size(); List list = new ArrayList<>(); for (int i = 0; i < n; i++) { TreeNode node = queue.poll(); list.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } ans.add(list); } return ans; } }

108.将有序数组转换为二叉树 题目

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

代码

class Solution { public TreeNode sortedArrayToBST(int[] nums) { return sortedArrayToBST(nums, 0, nums.length - 1); }

public TreeNode sortedArrayToBST(int[] nums, int left, int right) { if (left > right) return null; else if (left == right) return new TreeNode(nums[left]); else { int mid = (right - left >> 1) + left; TreeNode lchild = sortedArrayToBST(nums, left, mid - 1); TreeNode rchild = sortedArrayToBST(nums, mid + 1, right); return new TreeNode(nums[mid], lchild, rchild); } }

}

98.验证二叉搜索树 题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下：

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

class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, 0, 0, false, false); }

public boolean isValidBST(TreeNode root, int down, int up, boolean downExist, boolean upExist) { if (root == null) return true; if (downExist && root.val <= down) return false; if (upExist && root.val >= up) return false; boolean left = isValidBST(root.left, down, root.val, downExist, true); boolean right = isValidBST(root.right, root.val, up, true, upExist); return left && right; }

}

230.二叉搜索树中第K小的元素 题目

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。 思路：取中序遍历序列的下标为k-1的数。中序遍历，每遍历一个结点，计数+1，当计数为k时恰好为第k小的元素，递归中序遍历版，缺点是，相比于迭代遍历，下面的代码会遍历整棵树

代码

class Solution { int count = 0; int ans;

public int kthSmallest(TreeNode root, int k) { if (root == null) return 0; kthSmallest(root.left, k); count++; if (count == k) ans = root.val; kthSmallest(root.right, k); return ans; }

}

199.二叉树的右视图 题目

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

代码

class Solution { public List rightSideView(TreeNode root) { if (root == null) return new ArrayList<>(); Queue queue = new LinkedList<>(); List ans = new ArrayList<>(); queue.offer(root); while (!queue.isEmpty()) { int n = queue.size(); for (int i = 0; i < n; i++) { TreeNode node = queue.poll(); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); if (i == n - 1) ans.add(node.val); } } return ans; } }