一颗树,要么是空树,要么有两个指针,每个指针指向一棵树.树是一种递归结构,很多树的问题可以使用递归来解决!
二叉树的中序遍历
难度级别: 中等
递归实现
public static List<Integer> res;
public List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<>();
inOrderTraversal(root);
return res;
}
private void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
res.add(root.val);
inOrderTraversal(root.right);
}二叉树中序遍历非递归实现,数据结构:栈
public static List<Integer> res;
public List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<>();
inOrderTraversal(root);
return res;
}
private void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
res.add(root.val);
root = root.right;
}
}
System.out.println();
}对称二叉树
难度级别: 简单
对称二叉树的递归实现
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}对称二叉树的非递归实现,数据结构:队列(bfs)
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
queue.add(root);
while (!queue.isEmpty()) {
TreeNode t1 = queue.poll();
TreeNode t2 = queue.poll();
if (t1 == null && t2 == null) {
continue;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
queue.add(t1.left);
queue.add(t2.right);
queue.add(t1.right);
queue.add(t2.left);
}
return true;
}两种实现方法的时间复杂度为: O(n),空间复杂度: O(n)
树的高度
难度级别: 简单
求二叉树的最大深度递归实现
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1+ Math.max(maxDepth(root.left), maxDepth(root.right));
}求二叉树最大深度的非递归实现,用栈来实现,其中用到了Pair<K,V>,键值对映射.在javafx.util.Pair包中,需要导入!
private int depth = 0;
public int maxDepth(TreeNode root) {
Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
if (root != null) {
stack.add(new Pair<>(root, 1));
}
int depth = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.poll();
root = current.getKey();
int cur_depth = current.getValue();
if (root != null) {
depth = Math.max(depth, cur_depth);
stack.add(new Pair<>(root.left, cur_depth + 1));
stack.add(new Pair<>(root.right, cur_depth + 1));
}
}
return depth;
}平衡二叉树
难度级别: 简单
3
/ \
9 20
/ \
15 7true
1
/ \
2 2
/ \
3 3
/ \
4 4false
平衡树左右子树的高度差的绝对值不超过1,即小于等于1
private boolean res = true;
public boolean isBalanced(TreeNode root) {
maxDepth(root);
return res;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (Math.abs((left - right)) > 1) {
res = false;
}
return 1 + Math.max(left, right);
}平衡二叉树
难度级别: 简单
平衡二叉树: 平衡树的左右子树的高度差的绝对值小于等于1
平衡二叉树的递归实现
private boolean res = true;
public boolean isBalanced(TreeNode root) {
maxDepth(root);
return res;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (Math.abs((left - right)) > 1) {
res = false;
}
return 1 + Math.max(left, right);
}求二叉树的最小深度
二叉树的最小深度递归实现
难度级别: 简单
写法一
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if (left == 0 || right == 0) {
return left + right + 1;
}
return Math.min(left, right) + 1;
}写法二
public int minDepth(TreeNode root) {
return dfs(root);
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
//若不考虑以下两种情况,leetcode测试用例只能过去一部分
if (root.left == null) {
return 1 + minDepth(root.right);
}
if (root.right == null) {
return 1 + minDepth(root.left);
}
return 1 + Math.min(dfs(root.left), dfs(root.right));
}时间复杂度:O(n) ,n为节点的个数; 空间复杂度:O(n)
路径的和
leetcode112.路径的和(判断是否存在路径和等于一个数)
难度级别: 简单
路径总和递归实现
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null && root.val == sum) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}二叉树的前序遍历
难度级别: 中等
递归实现
static List<Integer> res;
public List<Integer> preorderTraversal(TreeNode root) {
res = new ArrayList<>();
preOrderTraversal(root);
return res;
}
private void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
res.add(root.val);
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}非递归实现,数据结构:栈
static List<Integer> res;
public List<Integer> preorderTraversal(TreeNode root) {
res = new ArrayList<>();
preOrderTravsersal(root);
return res;
}
private void preOrderTravsersal(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
res.add(root.val);
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
System.out.println();
}翻转二叉树
难度级别:简单
递归实现
public TreeNode invertTree(TreeNode root) {
if (root==null){
return null;
}
TreeNode left = root.left;
root.left = invertTree(root.right);
root.right =invertTree(left);
return root;
}打家劫舍III
难度级别: 中等
递归实现
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int val1 = root.val;
if (root.left != null) {
val1 += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val1 += rob(root.right.left) + rob(root.right.right);
}
int val2 = rob(root.left) + rob(root.right);
return Math.max(val1, val2);
}左叶子之和
leetcode404.左叶子之和(即求左子树叶子节点的和)
难度级别: 简单
递归实现
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
if (isLeaf(root.left)) {
return root.left.val + sumOfLeftLeaves(root.right);
}
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
private boolean isLeaf(TreeNode root) {
if (root == null) {
return false;
}
return root.left == null && root.right == null;
}路径总和
leetcode437.路径总和(即找出路径和等于给定数值的路径总数)
难度级别: 简单
递归实现
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int res = pathSumWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return res;
}
private int pathSumWithRoot(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int res = 0;
if (root.val == sum) {
res++;
}
res += pathSumWithRoot(root.left, sum - root.val) + pathSumWithRoot(root.right, sum - root.val);
return res;
}二叉树的直径
难度级别: 简单
递归实现
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return max;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
max = Math.max(max, (leftDepth + rightDepth));
return Math.max(leftDepth, rightDepth) + 1;
}另一个树的子树
leetcode572.另一个树的子树(即在一个树中找另个一个树 )
难度级别: 简单
递归实现
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) {
return false;
}
if (t == null) {
return false;
}
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null) {
return false;
}
if (t.val != s.val) {
return false;
}
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}合并两个二叉树
难度级别: 简单
递归实现
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
return mergeTwoTrees(t1, t2);
}
private TreeNode mergeTwoTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return null;
}
if (t1 == null && t2 != null) {
return t2;
}
if (t1 != null && t2 == null) {
return t1;
}
TreeNode root = new TreeNode((t1.val + t2.val));
root.left = mergeTwoTrees(t1.left, t2.left);
root.right = mergeTwoTrees(t1.right, t2.right);
return root;
}求二叉树中的第二小的节点
难度级别: 简单
递归实现
public int findSecondMinimumValue(TreeNode root) {
if (root == null) {
return -1;
}
if (root.left == null && root.right == null) {
return -1;
}
int leftVal = root.left.val;
int rightVal = root.right.val;
if (leftVal == root.val) {
leftVal = findSecondMinimumValue(root.left);
}
if (rightVal == root.val) {
rightVal = findSecondMinimumValue(root.right);
}
if (leftVal != -1 && rightVal != -1) {//左右节点都有第二最小值,求最小值
return Math.min(leftVal, rightVal);
}
if (leftVal != -1) {//只有左边有,否则返回右边
return leftVal;
}
return rightVal;
}最长同值路径
难度级别: 简单
递归实现
private int path = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return path;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
path = Math.max(path, (leftPath + rightPath));
return Math.max(leftPath, rightPath);
}使用 BFS 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。
一棵树每层节点的平均数