算法刷题5【剑指offer系列之树】

2020.06.04

1、前序中序重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：前序遍历根左右，中序遍历左根右，因此前序数组的第一个元素pre[0]就是根，可以按照这个根将中序数组分成左右两个部分。然后root.left在左部分，root.right在右部分。
（1）根据pre[0]新建结点，这个结点就是root
（2）遍历中序数组，找到root，然后开始递归；递归出口就是in.length==0||pre.length == 0
（3）返回root

注意copyOfRange是左闭右开的

public class ReconstructionTree {

    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        //base case
        if (pre==null||pre.length==0||in==null||in.length==0){
            return null;
        }else {
            TreeNode root=new TreeNode(pre[0]);
            //中序遍历寻找根
            for (int i=0;i<in.length;i++){
                if (root.val==in[i]){
                    //注意copyOfRange是左闭右开的
                    root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),
                            Arrays.copyOfRange(in,0,i));
                    root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length-1)
                    ,Arrays.copyOfRange(in,i+1,in.length));
                }
            }
            return root;
        }

    }
}

2、判断树B是否为A的子树

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：
（1）需要在A 树中查找到和B的根节点相同的结点，这个结点下面存在的子树就有可能和树B一样，查找的过程可以使用递归实现
（2）判断以第一步在A树中找到的结点为根的A1树是否存在子树和B树相等：注意递归的终止条件

(1） B树为空说明判断成功（A1树有可能还不为空的,因为子树可能是中间的部分）
（2） A1树为空但是B树不为空则判断失败

需要注意的是在树的取值操作之前要先判断是否为空，避免空指针异常。

public class HasSubtree {

    /**
     * 1、递归查找到和B的根节点相同的结点
     * 树的操作要一直想着指针不能为空
     *
     * @param root1
     * @param root2
     * @return
     */
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1==null||root2==null){
            return false;
        }
        boolean res = false;
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                res = judge(root1, root2);
            }
            //判断A的左树
            if (!res) {
                res = HasSubtree(root1.left, root2);
            }
            //判断A的右子树
            if (!res) {
                res = HasSubtree(root1.right, root2);
            }

        }
        return res;
    }

    /**
     * 2、判断A1树的子树和B树是否相等：注意递归的终止条件
     * （1） B树为空说明判断成功（A1树有可能还不为空的）
     * （2） A1树为空但是B树不为空则判断失败
     *
     * @param root1
     * @param root2
     * @return
     */
    private boolean judge(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 != null) {
            return false;
        }
        if (root2 == null) {
            return true;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return judge(root1.left, root2.left) && judge(root1.right, root2.right);
    }
}

3、操作给定的二叉树，将其变换为源二叉树的镜像

思路：核心思想就是遍历树的同时如果有子结点，则交换左右子结点。可以采用任何一种遍历方式，最简单的就是前序递归直接搞定。

public class Mirror {

    /**
     * 核心：遍历的同时，如果有左右子结点，则交换
     *
     * @param root
     */
    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        //说明是叶子节点
        if (root.left == null && root.right == null) {
            return;
        }
        //注意不是说左右孩子都有才能交换
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        if (root.left != null) {
            Mirror(root.left);
        }
        if (root.right != null) {
            Mirror(root.right);
        }
    }

    /**
     * 非递归：可以采用层次遍历:只要是遍历树就可以了
     * @param root
     */
    public void Mirror1(TreeNode root) {
        if (root==null){
            return;
        }
        ArrayDeque<TreeNode> queue=new ArrayDeque<>();
        TreeNode node=null,temp=null;
        queue.offer(root);
        while (!queue.isEmpty()){
            node=queue.poll();
            temp=node.left;
            node.left=node.right;
            node.right=temp;
            if (node.left!=null){
                queue.offer(node.left);
            }
            if (node.right!=null){
                queue.offer(node.right);
            }
        }
    }

}