树easy专题

本文最后更新于：2023年2月10日 上午

总结

  1. 树跟链表一样，很多场景可以使用递归求解

LeetCode94 二叉树的中序遍历 (yes)

（1）题目：

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

（2）思路：

-

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private List<Integer> result = new ArrayList<>();
/**
 * 前序：根左右
 * 中序：左根右
 * 后序：左右根
 */
public List<Integer> inorderTraversal(TreeNode root) {
    addTree(root);

    return result;
}

private void addTree(TreeNode root) {
    if (root == null) {
        return;
    }

    addTree(root.left);
    result.add(root.val);
    addTree(root.right);
}

LeetCode100 相同的树 (yes)

（1）题目：

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

（2）思路：

-

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q != null) {
        return false;
    }

    if (p != null && q == null) {
        return false;
    }

    if (p == null && q == null) {
        return true;
    }

    return p.val == q.val
            && isSameTree(p.left, q.left)
            && isSameTree(p.right, q.right);
}

LeetCode101 对称二叉树 (yes)

（1）题目：

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

（2）思路：

-

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }

    return symmetric(root.left, root.right);
}

private boolean symmetric(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    }

    if (left == null && right != null) {
        return false;
    }

    if (left != null && right == null) {
        return false;
    }

    return left.val == right.val && symmetric(left.right, right.left) && symmetric(left.left, right.right);
}

LeetCode104 二叉树的最大深度 (yes)

（1）题目：

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

（2）思路：

-

（3）代码：

1
2
3
4
5
6
7
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

LeetCode108 将有序数组转为二叉搜索树 (yes)

（1）题目：

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

（2）思路：

  • 只要左右子树是平衡二叉树，那么当前树就是平衡二叉树

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public TreeNode sortedArrayToBST(int[] nums) {
    if (null == nums || 0 == nums.length) {
        return null;
    }
    return buildBST(nums, 0, nums.length - 1);
}

public TreeNode buildBST(int[] nums, int s, int e) {
    if (s < 0 || e < 0 || s >= nums.length || e >= nums.length) {
        return null;
    }
    if (s == e) {
        return new TreeNode(nums[s]);
    }

    if (e - s == 1) {
        TreeNode left = new TreeNode(nums[s]);
        TreeNode root = new TreeNode(nums[e]);
        root.left = left;
        return root;
    }

    int mid = (e + s) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    TreeNode left = buildBST(nums, s, mid - 1);
    TreeNode right = buildBST(nums, mid + 1, e);
    root.left = left;
    root.right = right;
    return root;
}

/**
 * 官方解法，更简洁
 */
public TreeNode helper(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }

    // 总是选择中间位置左边的数字作为根节点
    int mid = (left + right) / 2;

    TreeNode root = new TreeNode(nums[mid]);
    root.left = helper(nums, left, mid - 1);
    root.right = helper(nums, mid + 1, right);
    return root;
}

LeetCode110 判断平衡二叉树 (no)

（1）题目：

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

（2）思路：

  • 自顶向下，暴力法，时间复杂度Nlongn
  • 自底向上，时间复杂度为N，最优解。思考：就是在遍历的过程中加上剪枝，当高度超过2，必定不是平衡树，-1这个结果会向上传递

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 自顶向下，暴力法，时间复杂度Nlongn
 */
public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }

    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
            && isBalanced(root.left) && isBalanced(root.right);
}
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

/**
 * 自底向上，时间复杂度为N，最优解
 * 思考：就是在遍历的过程中加上剪枝，当高度超过2，必定不是平衡树，-1这个结果会向上传递
 */
public boolean isBalanced2(TreeNode root) {
    return recur(root) != -1;
}
private int recur(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = recur(root.left);
    if (left == -1) {
        return -1;
    }
    int right = recur(root.right);
    if (right == -1) {
        return -1;
    }
    return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}

LeetCode111 二叉树最小深度 (no)

（1）题目：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

（2）思路：

  • 非递归解法，使用栈，先进先出
    • 记录当前层和下一层节点数量
    • 记录层的高度
    • 当节点的左右子节点为null，返回层的高度，因为是第一个遇到的，所以是最小高度
  • 递归解法
    • 左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
    • 如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度
    • 最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public int minDepth(TreeNode root) {
    if (null == root) {
        return 0;
    }
    Deque<TreeNode> nodes = new ArrayDeque<>();
    nodes.push(root);
    int level = 1;
    int countUp = 1;
    int countDown = 0;

    while (!nodes.isEmpty()) {
        TreeNode pop = nodes.removeFirst();
        countUp--;

        if (pop.left == null && pop.right == null) {

            return level;
        }
        if (null != pop.left) {
            nodes.addLast(pop.left);
            countDown++;
        }
        if (null != pop.right) {
            nodes.addLast(pop.right);
            countDown++;
        }

        if (countUp == 0) {
            countUp = countDown;
            countDown = 0;
            level++;
        }
    }
    return level;
}

public int minDepth1(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 这道题递归条件里分为三种情况
    // 1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
    if (root.left == null && root.right == null) {
        return 1;
    }
    // 2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度
    int m1 = minDepth(root.left);
    int m2 = minDepth(root.right);
    // 这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
    if (root.left == null || root.right == null) {
        return m1 + m2 + 1;
    }

    // 3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
    return Math.min(m1, m2) + 1;
}

LeetCode112 路径总和 (yes)

（1）题目：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

（2）思路：

  • 自己的思路

    • 自顶向下，依次计算经过节点的和，判断符合条件则跳出循环

  • 题解思路

    • 这道题提供了一种思路，求和sum，不一定非要+，也可以减
    • 就像这道题，是从根节点依次减去当前节点的val，然后判断==0

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private boolean res = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    curSum(root, 0, targetSum);
    return res;
}
/**
 * 从根节点当当前节点的和
 */
private void curSum(TreeNode root, int sum, int target) {
    if (root == null) {
        return;
    }

    sum += root.val;
    if (sum == target && null == root.left && null == root.right) {
        res = true;
        return;
    }

    curSum(root.left, sum, target);
    curSum(root.right, sum, target);
}

/**
 * 题解1：DFS解法
 * 这道题提供了一种思路，求和sum，不一定非要+，也可以减
 * 就像这道题，是从根节点依次减去当前节点的val，然后判断==0
 */
public boolean hasPathSum1(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) {
        return root.val == sum;
    }
    return hasPathSum1(root.left, sum - root.val) || hasPathSum1(root.right, sum - root.val);
}

LeetCode113 路径总和2 (yes)

（1）题目：

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

（2）思路：

  • 自己的思路
    • 自顶向下，dfs/回溯的思想
    • 回溯的关键是需要把在结果不符合的时候需要能够回到之前的状态
    • 最开始做的时候，在符合条件的地方只add，没有remove，这样会导致多条path时，后续的path会多节点，因为第一条path没有去除
    • 回溯的思想，有add就要有remove

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private List<List<Integer>> allPaths = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    count(root, targetSum, new ArrayList<>());
    return allPaths;
}

public void count(TreeNode root, int tar, List<Integer> path) {
    if (root == null) {
        return;
    }

    if (null == root.left && null == root.right && root.val == tar) {
        path.add(root.val);
        allPaths.add(new ArrayList<>(path));
      	// 注意这里，需要把结果存入的时候去除
        path.remove(path.size() - 1);
        return;
    }

    path.add(root.val);
    count(root.left, tar - root.val, path);
    count(root.right, tar - root.val, path);
    path.remove(path.size()-1);
}

LeetCode226 翻转二叉树 (yes)

（1）题目：

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

输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

（2）思路：

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return root;
    }

    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;

    return root;
}

LeetCode257 二叉树的所有路径 (yes)

（1）题目：

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

输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

（2）思路：

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<String> binaryTreePaths(TreeNode root) {
    if (null == root) {
        return res;
    }
    if (null == root.left && null == root.right) {
        res.add("" + root.val);
        return res;
    }
    printPath(root.left, "" + root.val);
    printPath(root.right, "" + root.val);
    return res;
}

List<String> res = new ArrayList<>();
public void printPath(TreeNode root, String path) {
    if (root == null) {
        return;
    }

    path += "->" + root.val;
    if (null == root.left && null == root.right) {
        res.add(path);
        return;
    }

    printPath(root.left, path);
    printPath(root.right, path);
}
刷题/Leetcode > 树
#LeetCode #easy #树
树easy专题
http://coder-xieshijie.cn/2023/02/07/刷题/树easy专题/
作者
谢世杰
发布于
2023年2月7日
更新于
2023年2月10日
许可协议