Leetcode刷题记

[Leetcode][Tree--2]树相关题目汇总/分析/总结

2019-06-25  本文已影响0人  奔跑的程序媛A
  1. Binary Tree Con.
    (6) Structure of Tree

    (7) SubTree/Leaves

    (8) Other BT

  2. BST(补充)

  3. Other Tree


[Binary Tree Con.][Structure of Tree]

#100 Same Tree

Easy

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

Time complexity : O(N), where N is a number of nodes in the tree, since one visits each node exactly once.

Space complexity : O(log(N)) in the best case of completely balanced tree and O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(!check(p, q)) return false;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.add(p);
        s2.add(q);
        while(!s1.isEmpty()){
            TreeNode n1 = s1.pop();
            TreeNode n2 = s2.pop();
            if(!check(n1,n2))
                return false;
            if(n1 != null) {
                s1.push(n1.left);
                s2.push(n2.left);
                s1.push(n1.right);
                s2.push(n2.right);
            }
        }
        return true;
    }
    public boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return true;
    }

Time complexity : O(N), where N is a number of nodes in the tree, since one visits each node exactly once.

Space complexity : O(log(N)) in the best case of completely balanced tree and O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.

#101 Symmetric Tree
    public boolean isSymmetric(TreeNode root) {
        return help(root, root);
    }
    public boolean help(TreeNode t1, TreeNode t2){
        if(t1 == null && t2 == null) return true;
        if(t1 == null || t2 == null) return false;
        if(t1.val == t2.val) return help(t1.left, t2.right) && help(t1.right, t2.left);
        return false;
    }

Time O(n)
Space O(n)

    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while(!q.isEmpty()){
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();
            if(t1 == null && t2 == null) continue;
            if(t1 == null || t2 == null) return false;
            if(t1.val != t2.val) return false;
            q.add(t1.left);
            q.add(t2.right);
            q.add(t1.right);
            q.add(t2.left);
        }
        return true;
    }

Time O(n)
Space O(n)

#965 Univalued Binary Tree
    public boolean isUnivalTree(TreeNode root) {
        if(root == null) return true;
        if(root.left != null || root.right != null){
            if(root.left == null) return root.val == root.right.val && isUnivalTree(root.right);
            if(root.right == null) return root.val == root.left.val &&isUnivalTree(root.left);
            return root.val == root.right.val && root.val == root.left.val && isUnivalTree(root.left) && isUnivalTree(root.right);
        }
        return true;
    }

Time: O(n)
Space: O(H) height

#958 Check Completeness of a Binary Tree
public boolean isCompleteTree(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int level = 0;
        while(!q.isEmpty()){
            int size = q.size();
            boolean check = true;
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                if(cur.left != null && size != 1 << level) return false;
                if(cur.left != null) {
                    if(!check) return false;
                    q.add(cur.left);
                }else check = false;
                if(cur.right != null) {
                    if(!check) return false;
                    q.add(cur.right);
                }else check = false;
            }
            level++;
        }
        return true;
    }

Time O(N)
Space O(N)

#951 Flip Equivalent Binary Trees
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return true;
        if(root1 == null || root2 == null) return false;
        if(root1.val == root2.val){
            boolean check1 = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
            boolean check2 = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
            boolean c = check1 || check2;
            return c;
        }else return false;
    }

Time O(min(n1, n2))
Space O(min(h1, h2))


[Binary Tree Con.][SubTree/Leaves]

#222 Count Complete Tree Nodes
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int res = 0;
        while(!q.isEmpty()){
            int size = q.size();
            res += size;
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
        }
        return res;
    }

Time O(n)
Space O(n)

    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int left_height = help(root.left);
        int right_height = help(root.right);
        if(left_height == right_height){
            return left_height == 0? 1 : (1 << left_height) - 1 + 1 + countNodes(root.right); 
        }else{
            return right_height == 0? countNodes(root.left) + 1:(1 << right_height) - 1 + 1 + countNodes(root.left); 
        }
    }
    public int help(TreeNode root){
        int height = 0;
        while(root != null){
            height++;
            root = root.left;
        }
        return height;
    }

Time O(log(n))
Space O(log(n))

#508 Most Frequent Subtree Sum
int max_count = 0;
    Map<Integer, Integer> sum_hash;
    Map<Integer, ArrayList<Integer>> count_hash;
    public int[] findFrequentTreeSum(TreeNode root) {
        sum_hash = new HashMap<>(); //<sum, count>
        help(root);
        ArrayList<Integer> re = new ArrayList<>();
        if(max_count == 0) return new int[0];
        for (Map.Entry<Integer, Integer> entry : sum_hash.entrySet()) {
            if(max_count == entry.getValue()){
                re.add(entry.getKey());
            }
        }
        int[] res = new int[re.size()];
        int i = 0;
        for(Integer a: re){
            res[i++] = a;
        }
        return res;
    }
    public int help(TreeNode root){
        if(root == null) return 0;
        int sum = help(root.left) + help(root.right) + root.val;
        if(sum_hash.containsKey(sum)){
            sum_hash.put(sum, sum_hash.get(sum)+1);
        }else{
            sum_hash.put(sum, 1);
        }
        if(sum_hash.get(sum) > max_count) max_count = sum_hash.get(sum);
        return sum;
    }
#993 Cousins in Binary Tree
    TreeNode parent = null;
    public boolean isCousins(TreeNode root, int x, int y) {
        int find_x = find(root, x, 1, parent);
        TreeNode parent_x = null;
        if(parent != null) parent_x = parent;
        
        parent = null;
        int find_y = find(root, y, 1, parent);
        TreeNode parent_y = null;
        if(parent != null) parent_y = parent;
        return find_x == find_y && parent_x != parent_y;
    }
    public int find(TreeNode root, int cur, int level, TreeNode parent){
        if(root == null) return 0;
        if(root.val == cur){
            this.parent = parent;
            return level;
        }
        int ld = find(root.left, cur, level+1, root);
        if(ld != 0) return ld;
        return find(root.right, cur, level + 1, root);
    }

Time O(n)
Space O(h)


[Binary Tree Con.][Other BT]

#116 Populating Next Right Pointers in Each Node
    public Node connect(Node root) {
        if(root == null || root.left == null) return root;
        root.left.next = root.right;
        if(root.next!=null)
            root.right.next = root.next.left;
        connect(root.left);
        connect(root.right);
        return root;
    }

Time O(n)
Space O(1)

    public Node connect(Node root) {
        if(root==null) return root;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            Node previous = null;
            for(int i = 0; i < size; i++){
                Node cur = q.poll();
                if(previous != null) previous.next = cur;
                previous = cur;
                if(cur.left!=null) q.offer(cur.left);
                if(cur.right!=null) q.offer(cur.right);
            }
        }
        return root;
    }

Time O(n)
Space O(n)

#117 Populating Next Right Pointers in Each Node II
    public Node connect(Node root) {
        if(root==null) return root;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            Node previous = null;
            for(int i = 0; i < size; i++){
                Node cur = q.poll();
                if(previous != null) previous.next = cur;
                previous = cur;
                if(cur.left!=null) q.offer(cur.left);
                if(cur.right!=null) q.offer(cur.right);
            }
        }
        return root;
    }

Time O(n)
Space O(n)

    public Node connect(Node root) {
        Node dummy = new Node();
        Node pre = dummy;
        Node cur = root;
        while(cur != null){
            if(cur.left != null){
                pre.next = cur.left;
                pre = pre.next;
            }
            if(cur.right != null){
                pre.next = cur.right;
                pre = pre.next;
            }
            cur = cur.next;
            if(cur == null){
                pre = dummy;
                cur = pre.next;
                dummy.next = null; //keep dummy is new Node();
            }
        }
        return root;
}

Time O(n)
Space O(1)

#236 Lowest Common Ancestor of a Binary Tree
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        res = null;
        help(root, p, q);
        return res;
    }
    public boolean help(TreeNode root, TreeNode p, TreeNode q){
        if(root == null) return false;
        int left = help(root.left, p, q) ? 1 : 0;
        int right = help(root.right, p, q) ? 1 : 0;
        int mid = (root.val == p.val || root.val == q.val) ? 1 : 0;
        if(left + right + mid >=2){
            res = root;
        }
        return left + right + mid > 0;
    }

Time O(n)
Space O(n)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        Map<TreeNode,TreeNode> map = new HashMap<>(); //node, parent
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        map.put(root, null);
        while(!map.containsKey(p) || !map.containsKey(q)){
            TreeNode cur = s.pop();
            if(cur.left != null){
                map.put(cur.left, cur);
                s.push(cur.left);
            }
            if(cur.right != null){
                map.put(cur.right, cur);
                s.push(cur.right);
            }
        }
        
        Set<TreeNode> back = new HashSet<>();
        while(p != null){
            back.add(p);
            p = map.get(p);
        }
        while(!back.contains(q)){
            q = map.get(q);
        }
        return q;
    }

Time O(n)
Space O(n)

#297 Serialize and Deserialize Binary Tree

可以与449. Serialize and Deserialize BST比较做

// Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        ser_help(sb, root);
        return sb.toString();
    }
    public void ser_help(StringBuilder sb, TreeNode root){
        if(root == null){
            sb.append("*").append(",");
            return;
        }
        sb.append(root.val).append(",");
        ser_help(sb, root.left);
        ser_help(sb, root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> q = new LinkedList<>();
        q.addAll(Arrays.asList(data.split(",")));
        return des_help(q);
    }
    public TreeNode des_help(Queue<String> q){
        String cur = q.poll();
        if(cur.equals("*")) return null;
        TreeNode root = new TreeNode(Integer.valueOf(cur));
        root.left = des_help(q);
        root.right = des_help(q);
        return root;
        
    }

[BST(补充)]

#235 Lowest Common Ancestor of a Binary Search Tree
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }

Time O(n)
Space O(n)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int p_val = p.val, q_val = q.val;
        TreeNode cur = root;
        while(cur != null){
            if(cur.val < p_val && cur.val < q_val) cur = cur.right;
            else if(cur.val > p_val && cur.val > q_val) cur = cur.left;
            else return cur;
        }
        return null;
    }

Time O(n)
Space O(1) 不需要stack因为不需要backtrack


[Others]

#337 House Robber III
    public int rob(TreeNode root) {
        if(root == null) return 0;
        int[] res = new int[2];
        res = help(root);
        return Math.max(res[0], res[1]);
    }
    public int[] help(TreeNode root){
        int[] res = new int[2];
        if(root == null){
            res[0] = 0;
            res[1] = 0;
            return res;
        }
        int[] left = help(root.left);
        int[] right = help(root.right);
        res[0] = root.val + left[1] + right[1];
        res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return res;
    }
#834 Sum of Distances in Tree

Hard

    List<Set<Integer>> tree;
    int N;
    int[] res, count;
    public int[] sumOfDistancesInTree(int N, int[][] edges) {
        tree = new ArrayList<>();
        this.N = N;
        res = new int[N];
        count = new int[N];
        Arrays.fill(count, 1);
        for(int i = 0; i < N; i++){
            tree.add(new HashSet<>());
        }
        for(int[] edge: edges){
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
        }
        dfs(0, -1);
        dfs2(0, -1);
        return res;
    }
    public void dfs(int node, int parent){
        for(int child: tree.get(node)){
            if(child != parent){
                dfs(child, node);
                count[node] += count[child];
                res[node] += res[child] + count[child];
            }
        }
    }
    public void dfs2(int node, int parent){
        for(int child: tree.get(node)){
            if(child != parent){
                res[child] = res[node] - count[child] + N - count[child];
                dfs2(child, node);
            }
        }
    }
#310 Minimum Height Trees
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Set<Integer>> tree = new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        if (edges.length == 0) {
            res.add(0);
            return res;
        }
        int[] indegree = new int[n];
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++)
        {
            tree.add(new HashSet<>());
        }   
        for(int[] edge: edges){
            tree.get(edge[0]).add(edge[1]);
            tree.get(edge[1]).add(edge[0]);
        }
        for(int i = 0; i < n; i++){
            indegree[i] = tree.get(i).size();
            if(indegree[i] == 1) q.add(i);
        }
        int count = 0;
        while(!q.isEmpty()){
            int size = q.size();
            count += size;
            for(int i = 0; i < size; i++){
                int cur = q.poll();
                indegree[cur]--;
                if(count == n) {
                    res.add(cur);
                }
                for(Integer node: tree.get(cur)){
                    if(indegree[node]!=0){
                        indegree[node]--;
                        if(indegree[node] == 1) q.add(node);
                    }
                }
            }
        }
        return res;
    }
** 558* Quad Tree Intersection
    public Node intersect(Node quadTree1, Node quadTree2) {
        if(quadTree1.isLeaf){
            return quadTree1.val ? quadTree1 : quadTree2;
        }else if(quadTree2.isLeaf){
            return quadTree2.val ? quadTree2 : quadTree1;
        }
        Node TL = intersect(quadTree1.topLeft, quadTree2.topLeft);
        Node TR = intersect(quadTree1.topRight, quadTree2.topRight);
        Node BL = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        Node BR = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
        if(TL.isLeaf && TR.isLeaf && BL.isLeaf && BR.isLeaf && TL.val == TR.val && TL.val == BL.val && TL.val == BR.val) 
            return new Node(TL.val, true, null, null, null, null);
        Node res = new Node(false, false, TL, TR, BL, BR);
        return res;
    }
上一篇下一篇

猜你喜欢

热点阅读