算法问题——树集合相关问题

剑指 Offer 55 - II. 平衡二叉树

/**
 * Copyright (C), 2018-2020
 * FileName: isBalanced
 * Author:   xjl
 * Date:     2020/8/14 16:19
 * Description: 是否为平衡树
 */
package Tree;

public class isBalanced {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    /**
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
     * 如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
     *
     * @param root
     * @return
     */
    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;
        //判断是否为左和右边的节点数据超过的2
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

剑指 Offer 26. 树的子结构

/**
 * Copyright (C), 2018-2020
 * FileName: isSubStructure
 * Author:   xjl
 * Date:     2020/8/14 16:25
 * Description:
 */
package Tree;

public class isSubStructure {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //递归出口
        if (A == null || B == null) {
            return false;
        }
        /**
         * 保证其中一个就可以了成立就可以
         */
        return help(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    /**
     * 判断是否相同
     * @param A
     * @param B
     * @return
     */
    private Boolean help(TreeNode A, TreeNode B) {
        //当比较B结束 那么就是
        if (B == null) return true;
        //B已经不是空 但是A为空的时候B还没有搞完
        if (A == null) return false;
        //保证值相等 而且要保证是的是左子树等于左子树 右子树等于右子树
        return A.val == B.val && help(A.left, B.left) && help(A.right, B.right);
    }
}

剑指 Offer 07. 重建二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
        //输入的是前序遍历的结果 中序遍历的结果
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //递归函数的出口是
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        //获取到根节点的value的值
        TreeNode root = new TreeNode(preorder[0]);
        //构建left right子树
        int index = findIndex(preorder, inorder);
        // root.left = buildTree( 左子树的前序数组 左子树的中序数组);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, index+1), Arrays.copyOfRange(inorder, 0, index));
        //root.right = buildTree(右子树的前序数组 右子树的中序数组);
        root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length));

        return root;
    }

    //为了找到中序遍历的过程中位置
    private int findIndex(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                return i;
            }
        }
        return 0;
    }
}

剑指 Offer 55 - I. 二叉树的深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
       if(root == null) return 0;
        int left=maxDepth(root.left);
        int ringht=maxDepth(root.right);
        return Math.max(left,ringht) + 1;
    }
}

剑指 Offer 28. 对称的二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

剑指 Offer 68 - II. 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       //首先要检查当前的root情况，若为null就直接返回；
       //若为p、q则是满足最近公共节点为节点本身
       if(root == null || root == p || root == q)
            return root;
        //再利用递归从根节点开始，开始向下遍历每个节点（以下两步则为具体对每一个节点的左右子树查找），由上述if语句的返回值得到这两个节点的值
       TreeNode left = lowestCommonAncestor(root.left,p,q);
       TreeNode right = lowestCommonAncestor(root.right,p,q); 
       
       //对于left和right节点返回的情况，如果根节点的左子树/右子树找不到最近公共节点，那么就说明在右子树/左子树当中
       if(left == null)
            return right;
        
        if(right == null)
            return left;
        //如果上述两个情况都不符合 则说明根节点就是最近公共节点，直接返回
        return root;
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List levelOrder(TreeNode root) {
        List ans = new ArrayList();
        Queue queue = new LinkedList();
        queue.add(root);
        int sum = 1;
        while (!queue.isEmpty() && root != null) {
            List list = new LinkedList();
            int temp = 0;
            while (sum > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    temp++;
                    queue.add(node.left);
                }
                if (node.right != null) {
                    temp++;
                    queue.add(node.right);
                }
                sum--;
            }
            sum = temp;
            ans.add(list);
        }
        return ans;
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //可以采用的是的中序遍历的然后在从后向前找到第K个
    int res,k;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        dfs(root);
        return res;
    }
    //函数就是模拟了中序遍历的思想
    public void dfs(TreeNode root){
        if(root==null){return;}
        dfs(root.right);
        if(k==0){return;}
        if(--k==0){
            res=root.val;
        }
        dfs(root.left);
    }
}

572. 另一个树的子树

/**
 * Copyright (C), 2018-2020
 * FileName: isSubtree572
 * Author:   xjl
 * Date:     2020/8/21 9:46
 * Description: 子树
 */
package Tree;

public class isSubtree572 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean isSubtree(TreeNode A, TreeNode B) {
        if (A == null && B == null) return true;
        if (A == null || B == null) return false;
        return slove(A, B) || isSubtree(A.left, B) || isSubtree(A.right, B);
    }

    private boolean slove(TreeNode s, TreeNode t) {
        if (t == null && s == null)
            return true;
        else if (t == null || s == null)
            return false;
        else if (t.val == s.val)
            return slove(s.left, t.left) && slove(s.right, t.right);
        else
            return false;
    }

    public boolean isSubtree1(TreeNode s, TreeNode t) {
        if (t == null) return true;   // t 为 null 一定都是 true
        if (s == null) return false;
        return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
    }


    public boolean isSameTree(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 isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}

111. 二叉树的最小深度

/**
 * Copyright (C), 2018-2020
 * FileName: minDepth
 * Author:   xjl
 * Date:     2020/8/21 9:41
 * Description: 二叉树的最小深度
 */
package Tree;

import java.util.LinkedList;
import java.util.Queue;

public class minDepth {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 就是去找层序遍历找到最小的层数量
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue q = new LinkedList();
        q.offer(root);
        // root 本⾝就是⼀层， depth 初始化为 1
        int depth = 1;
        while (!q.isEmpty()) {
            int sz = q.size();
            /* 将当前队列中的所有节点向四周扩散 */
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                /* 判断是否到达终点 */
                if (cur.left == null && cur.right == null)
                    return depth;
                /* 将 cur 的相邻节点加⼊队列 */
                if (cur.left != null)
                    q.offer(cur.left);
                if (cur.right != null)
                    q.offer(cur.right);
            }
            /* 这⾥增加层数 */
            depth++;
        }
        return depth;
    }
}

538. 把二叉搜索树转换为累加树

/**
 * Copyright (C), 2018-2020
 * FileName: convertBST538
 * Author:   xjl
 * Date:     2020/8/21 12:47
 * Description:
 */
package Tree;

import java.util.LinkedList;

public class convertBST538 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        return dfs(root);
    }

    private TreeNode dfs(TreeNode root) {
        if (root == null) {
            return null;
        }
        LinkedList stack=new LinkedList();
        TreeNode node=root;
        int sum=0;
        while (node!=null||!stack.isEmpty()){
            while (node!=null){
                stack.add(node);
                node=node.right;
            }
            TreeNode temp=stack.pollLast();
            sum+= temp.val;
            temp.val=sum;
            node=temp.left;
        }
        return root;
    }

    int sum = 0;
    public TreeNode convertBST2(TreeNode root) {
        if(root != null){
            convertBST(root.right);
            sum = sum + root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}