二叉树的相关oj题目 — java实现

题目

翻转二叉树

翻转二叉树

二叉树的问题一般都需要用到递归。

递归则需要我们将问题转换成子问题，并且需要一个结束条件

所以翻转整个二叉树有两个步骤：

1. 先将 该树的左子树 和 右子树互换

2. 递归翻转二叉树的左子树和右子树
   而结束条件是 一个树为一颗空树。

接下来只需要根据步骤来就可以了。

注意这里不是换 节点当中 的val，而是换整个节点。（也可以说是左子树和右子树互换）

最后翻转好了返回 root 即可。

最后这里也可以做个小优化，就是如果 这个树的左子树和右子树都是空树的话就可以直接 root，这样就不会进行 null 和 null 的无效交换

/**
 * Definition for a binary tree node.
 * 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;
 * }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        if (root.left == null && root.right == null) {
            return root;
        }
        // 节点互换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        // 递归
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

判断两颗树是否相同

判断两颗树是否相同

还是利用递归来做

判断两颗树是否相同需要下面几个条件：

1. 判断两棵树的根是否相同
2. 递归判断左子树和右子树是否相同

只有都相同了，才能说明两树相同，只要有一处不相同，那么就不相同。

如果两树都是空树，那么两树一定是相等的。

如果两数当中仅有一树为空，那么两树一定不相等

此时，如果没有进入这两个 if 说明此时两树一定都不为空。

这个时候需要判断两树的根的值是否相等，如果不等，那么就直接说明两树不相等

最终就只需要满足一个条件那么两树就相等了，左子树和右子树都相等。

也可以优化写成这种。

前面的一处也可以进行优化

因为一旦前面的if 没有进去，那么两个树一定不都为空

/**
 * Definition for a binary tree node.
 * 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;
 * }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 两树都为空，则一定相等
        if (p == null && q == null) {
            return true;
        }

        // 两树仅有一个树为空，一定不相等
        if (p == null && q != null
                || p != null && q == null) {
            return false;
        }

        // 两树的根节点的值不相同时，一定不相等
        if (p.val != q.val) {
            return false;
        }

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

    }
}

对称二叉树

判断是否是对称二叉树

这个题是没办法用一个函数去递归做的。

当一颗二叉树的左子树和右子树 互相是翻转二叉树，那么则可以说这棵树是对称二叉树

如果是空树，那么则是对称二叉树。

然后我们只需要返回 该树的左子树和右子树是不是翻转二叉树即可。

对于判断翻转二叉树函数来说，跟我们刚才的那道判断两树是否相等有点类似

只不过就是最后不一样，一个是左子树等于左子树，右子树等于右子树；
另一个左子树等于右子树，右子树等于左子树。

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {

    //判断是否是对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

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

    //判断两颗树是否为翻转二叉树
    public boolean is(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;
        }

        //只有p的左子树等于q的右子树
        //p的右子树等于左子树相等，说明为翻转二叉树，否则不是
        return is(p.left, q.right) && is(p.right, q.left);
        
    }
}

判断一棵二叉树是否为另一颗的子树

判断一颗二叉树是否为另一颗的子树

思路：

还是需要用到递归的思路。

当一棵树的与另一棵树相等或与其左子树或右子树相等时，就可以说，这棵树是另一颗树的子树。

首先我们要知道一个前提条件，当两棵树的任意一棵树如果为空树，那么就不是子树了。

这个也是我们的递归的结束条件。

这个题目要用到两棵树是否相等的函数，刚才我们已经写过了，所以直接拿来用。

然后我们只需要判断是不是满足下列要求当中的一个即可：

1. 要么两树相等
2. 要么左子树与另一棵树相等
3. 要么右子树与另一棵树相等

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return false;
        }
    
        return isSameTree(p, q) || isSubtree(p.left, q) || isSubtree(p.right, q);
    }


    public boolean isSameTree(TreeNode p, TreeNode q) {
//1.先判断结构是否是一样的
        if(p != null && q == null || p == null && q != null) {
            return false;
        }
//上述if语句 如果没有执行，意味着两个引用 同时为空 或者同时不为空
        if(p == null && q == null) {
            return true;
        }
//都不为空 判断值是否一样
        if(p.val != q.val) {
            return false;
        }
//都不为空且值一样
        return isSameTree(p.left,q.left) &&  isSameTree(p.right,q.right);
    }
}

平衡二叉树

判断平衡二叉树

平衡二叉树是指的是所有节点的左子树和右子树的深度差不超过1.

方法1：

暴力获取每个节点的左子树和右子树的深度差。

注意每次需要特判 root是否为null，同时也是递归的结束条件

尽量不要函数套在函数里面，因为如果该函数得到的变量用到多次，那么就会重复进入函数，浪费时间，而且getHeight函数还是一个递归的函数

接着只需要写getHeight函数

一个树的高度等于，左子树的高度和右子树的高度的最大值 + 1

所以很好写

方法2：（更快）

方法1的时间复杂度有点高，遍历的每个节点都需要递归求该树的高度。

方法2思路：

在获取两颗子树的高度时顺便检查是否满足平衡二叉树

规定了如果返回的高度是-1则不满足条件，满足则返回该树的高度

判断左子树和右子树是否满足平衡二叉树，有一颗不满足，则直接不满足，两子树若都满足平衡二叉树，则判断两颗子树的深度差。

二叉树的层序遍历

二叉树的层序遍历

在进行特判时，不能返回null，需要返回一个空集合

这里的ArrayList集合也可以换成其他任意 实现List接口的集合

层序遍历有一个通用的模版

只需要将这个模版稍作修改即可

对于该题目来说，需要将每一层的所有节点的值存到集合当中

正常模版是每次弹出一个元素，但该题目需要每次弹出一整层的节点（正常模版也可以每次弹出一整层，都是一样的）

最后返回 ans 集合即可

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
 
        List<List<Integer>> res = new ArrayList<>();//实现List接口的集合都可以
        if (root == null) {
            return res;//需要返回空集合而不是null
        }

        Queue<TreeNode> queue = new LinkedList<>();//实现Queue接口的集合都可以
        queue.offer(root);//将根节点入队列

        while (!queue.isEmpty()){//栈不为空
            List<Integer> list = new ArrayList<>();
            int size = queue.size();//该层的节点数
            
            while (size > 0) {//
                TreeNode top = queue.poll();
                list.add(top.val);
                if (top.left != null) {
                    queue.offer(top.left);
                }
                if (top.right != null) {
                    queue.offer(top.right);
                }
                size--;//*
            }
            
            res.add(list);
        }

        return res;
    }
}

最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

三个点代表可能存在某棵树，假设p 和 q 分别为所求公共祖先的两个节点，root为树的根节点

方法1：

思路是分情况后，利用递归解决

有下列几种情况

1. 空树没有公共祖先

2. 根节点为 p 或 q

假设根节点为 p节点时，共有三种情况，在左子树里、在右子树里或者在A 节点的上方（前提如果存在）

根节点为q节点 同理。

这种情况下，它们的最近的公共祖先就是 根节点 root

3. 刚才的第2种情况已经考虑完所有关于根节点的情况，接下来的情况根节点不再跟p q有关，其中left 是左子树返回的节点，right同理
   

代码如下：

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {//空树没有公共祖先
            return null;
        }
        if (root == p || root == q) {//先考虑根节点
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null) {
            return right;
        }

        if (right == null) {
            return left;
        }
        return root;
    }

方法2：

思路：

1. 遍历所有节点，用哈希表存储 每个节点的父节点
2. 从p节点往上遍历，把遍历的节点加到另一个哈希表里
3. 此时向上遍历 q节点，如果 q节点在 哈希表当中存在，则该节点为最最近的公共祖先

 
本次需要用到的集合

 

第一步遍历我们可以用深度优先遍历（dfs），也可以想成子问题递归，由于有递归需要封装成一个函数

接着按照刚才的三个步骤即可

注意这里的while循环里 不是 q != root 和 p != root，而是 != null，如果是 != root，那么root不会放到hashSet集合里。

**当哈希表给一个不存在的值时会返回null，所以当放到 root的时候会返回null, 所以此时p == null会跳出循环

class Solution {
    Map<TreeNode, TreeNode> parent = new HashMap<>();//存储每个节点的父节点  
    Set<TreeNode> hashSet = new HashSet<>();//用于临时存储部分节点

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //1.将每个节点的父节点存储下来
        dfs(root);

        //2.将p节点的祖宗们放到另一个哈希表里
        while (p != null) {
            hashSet.add(p);
            p = parent.get(p);
        }

        //3.遍历q节点和他的祖宗们，出现的第一个重复的节点就是最近的公共祖先
        while (q != null) {
            if (hashSet.contains(q)) {
                return q;
            }
            q = parent.get(q);
        }

        //走到这里说明 q的祖宗们都不是 p 的祖宗们，所以没有公共祖先
        return null;
    }

    public void dfs(TreeNode root) {
        if (root == null) {//空树直接返回
            return;
        }

        if (root.left != null)  {
            parent.put(root.left, root);//root.left的父亲是root
            dfs(root.left);
        }

        if (root.right != null) {
            parent.put(root.right, root);//root.right的父亲是root
            dfs(root.right);
        }

    }
}

二叉树的构建和遍历

二叉树的构建

创建一个TreeNode类

主函数里只需要创建好树之后中序遍历即可

该题重点在于如何将先序遍历字符串变成一棵二叉树，就是createTree函数

大致思路：

1. 需要一个下标 index 用于指向字符串中的字符
2. 创建一个节点，节点的值为 字符串中 index下标的值
3. 子问题递归，该节点的左子树和右子树则等于 index++时的函数

根据一棵树的前序遍历与中序遍历构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树

知识点：

1. 前序遍历的遍历优先度是 根 > 左 > 右，本题中我们需要从头开始把前序遍历的数字按个当成根
2. 在中序遍历中，遍历优先度是 左 > 根 > 右，一个节点的左边的节点，一定在他的左子树里，右边的节点同理
   比如节点4的左边节点，那么就一定都在4节点的左子树里，右边的节点都在右子树里

大致思路：

1. 需要一个下标变量指向中序遍历的数组，记为preindex
2. 创建值为 preorder[preindex]的节点，作为整棵树的根节点
3. 找到该 根节点在中序遍历序列的位置
4. 递归处理

由于递归的时候需要给一个inorder数组的序列范围，所以需要另写一个函数

注意事项：
preindex 不放在函数的参数里，因为这样递归在归的时候，preindex就会还原，而正确情况应该是下标从0开始一直到数组inorder 的结尾下标

preindex需要放在外面当做成员变量，注意这里的preIndex 不要用 static 修饰，因为静态变量只要类被加载了，那么就会一直存在，所以第二个测试用例对象及以后的 preIndex的值 不等于0
 

先递归左子树，再递归右子树，因为前序遍历的优先度是 根 左 右。

时间优化：

find函数需要遍历完 下标 inst 到 ined，每次都需要遍历一遍非常耗时间，所以我们可以将中序遍历的值和下标的对应关系存起来

我们可以利用HashMap存储对应 关系

接下来只需要将 init 函数放在最初的函数中，并且把find 函数替换掉即可

public Map<Integer, Integer> relation = new HashMap<>();

    public void init(int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            relation.put(inorder[i], i);
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        init();
        return bulidTreeChild(preorder, inorder, 0, inorder.length - 1);
    }


    public int preIndex = 0;//前序遍历中的即将作为根节点的下标，可以不赋值，默认是0  
    // 返回数组下标从 inst 到 ined 的中序遍历 所构成的二叉树
    public TreeNode bulidTreeChild(int[] preorder, int[] inorder, int inst, int ined) {
        if (inst > ined) {//递归的结束条件
            return null;
        }

        //创建根节点
        TreeNode root = new TreeNode(preorder[preIndex]);
        //rootIndex是根节点在中序遍历里的下标
        int rootIndex = relation.get(root.val);//也可以写preorder[preIndex]
        preIndex++;//用一个根节点后 下标++;

        //根节点的左子树和右子树 子递归实现
        root.left = bulidTreeChild(preorder, inorder, inst, rootIndex-1);
        root.right = bulidTreeChild(preorder, inorder, rootIndex+1, ined);

        return root;
    }

    //找对应节点的下标
    public int find(int[] inorder, int inst, int ined, int val) {
        for (int i = inst; i <= ined; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

根据一棵树的中序遍历与后序遍历构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树

本题大致思路和刚才的前序中序遍历构造二叉树差不多

后序遍历的序列的最后一个值 是 整棵树的根节点

大致思路：

1. 定义一个变量postIndex 指向 postorder数组的最后一个元素
2. 创建一个值为postorder[postIndex]的节点作为根节点
3. 找到该节点在中序遍历序列中的位置，postIndex–;
4. 递归，并且是先递归右子树，再左子树，因为后序遍历的优先度是左右根，由于postindex是从大到小遍历的，所以右的优先度比左高，所以先递归左子树

根据二叉树创建字符串

根据二叉树创建字符串

大致思路：

1. 在所给函数中创建一个StringBuilder对象记为sb，另写一个需要递归的函数并且参数中含有该对象，最后返回调用该对象的toString的值即可
2. 将根节点的值拼接到sb，利用递归将左子树和右子树进行拼接

完