7.8号刷题

发表于 | 分类于 | 0 comments

第一题 108. Convert Sorted Array to Binary Search Tree

题目描述

将排序好的数组转化为平衡的排序二叉树

算法

找到中间的值，然后以中间的值为当前root节点的val

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class sortedArrayToBST108 {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        TreeNode root = helper(nums, 0, nums.length - 1);
        return root;
    }
    public TreeNode helper(int[] nums, int low, int high) {
        if (low > high) return null;
        int mid = low + (high - low) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, low, mid - 1);
        root.right = helper(nums, mid + 1, high);
        return root;
    }
}

第二题 109. Convert Sorted List to Binary Search Tree

题目描述

将List转化为平衡的排序二叉树

算法

与上一题相似，只是现在我们用一个slow和fast两个指针进行推进，当fast直到我们所需要的节点的时候，slow节点将刚好在中间这个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class sortedListToBST109 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return helper(head, null);
    }
    public TreeNode helper(ListNode left, ListNode right) {
        if (left == right) return null;
        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = helper(left, slow);
        root.right = helper(slow.next, right);
        return root;
    }
}

第三题 250. Count Univalue Subtrees

题目描述

查看一棵树中有多少值相同的子树

算法

注意一个地方，只要查看一棵树左右的值即可，不需要查看整课子树的相同的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    int count = 0;
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) return count;
        helper(root);
        return count;
    }
    public boolean helper(TreeNode root) {
        if (root == null) return true;
        boolean leftTag = helper(root.left);
        boolean rightTag = helper(root.right);
        if (leftTag && rightTag) {
            if (root.left != null && root.val != root.left.val) return false;
            if (root.right != null && root.val != root.right.val) return false;
            count++;
            return true;
        }
        else return false;
    }
}

第四题 572. Subtree of Another Tree

题目描述

给定两个非空二叉树s和t，判断t是否是s的子树。s的子树是指由s中某节点及该节点的所有子节点构成的二叉树。

特别的，s是其本身的子树

算法

在检查子树的时候，可以有两个回溯，一个检查所有的子树。另一个回溯检查当前子树的可行性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class isSubtree572 {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        if (helper(s, t)) return true;
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    public boolean helper(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        if(s.val != t.val) return false;
        return helper(s.left, t.left) && helper(s.right, t.right);
    }
}