投稿
  1. 极客之音首页
  2. 后端开发

二叉树OJ题讲解

小半 • • 后端开发 • 阅读 658

导读：本篇文章讲解 二叉树OJ题讲解，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

二叉树OJ题讲解

1. 前中后序遍历

前序遍历OJ链接
中序遍历OJ链接
后序遍历OJ链接

1.1 递归实现

在前序遍历中：
以下两种方法是等价的，但是并没有利用到返回值List<Integer>： （遍历思路）
在这里插入图片描述
利用到返回值List<Integer>的方法： （子问题思路）
在这里插入图片描述

中序遍历和后序遍历同。

1.2 非递归实现

利用一个栈来实现：
前序遍历：
在这里插入图片描述

中序遍历：
在这里插入图片描述

后序遍历：
在这里插入图片描述

2. 层序遍历

OJ链接

我们已经知道可以利用一个队列来进行层序遍历，但是此OJ题的关键是要求存放在List<List<Integer>>里面，那么我们该怎么判断二叉树的每一层？

代码实现：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);

        while(!qu.isEmpty()){
            int size = qu.size();
            List<Integer> tmp = new LinkedList<>();
            while(size > 0){
                TreeNode cur = qu.poll();
                size--;
				tmp.add(cur.val);
                if(cur.left != null){
                    qu.add(cur.left);
                }
                if(cur.right != null){
                    qu.add(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
}

3. 相同的树

OJ链接

思路：
1.判断结构是否相同，2.判断值是否相同：
一个为空一个不为空时结构不同；
若结构相同：都为null时，返回true；都有值时，判断值是否相同。
值不同false；值相同再判断左右子树。

代码实现：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        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);
    }
}

时间复杂度：
O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。

4. 另一棵树的子树

OJ链接

思路：
时刻注意避免空指针异常！
1.root或subRoot为空，返回false；
2.先判断两棵树是否为相同树；
3.subRoot是不是root.left子树；
4.subRoot是不是root.right子树；
5.否则 return false。
（判断两树是否相同时，用到了上题代码）

代码实现：

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // root或subRoot为空，返回false
        if(root == null || subRoot == null){
            return false;
        }
        // 2.先判断两棵树是否为相同树
        if(isSameTree(root,subRoot)){
            return true;
        }
        // 3.subRoot是不是root.left子树
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        // 4.subRoot是不是root.right子树
		if(isSubtree(root.right,subRoot)){
            return true;
        }
        // 5.false;
        return false;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        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);
    }
}

时间复杂度：
对于每一个 s 上的点，都需要做一次深度优先搜索来和 t 匹配，匹配一次的时间代价是O(∣t∣)，那么总的时间代价就是 O(∣s∣×∣t∣)。故渐进时间复杂度为 O(∣s∣×∣t∣)。

5. 翻转二叉树

OJ链接

思路：
翻转整棵树，其实就是翻转所有根节点的左子树和右子树。（交换地址）
1.翻转root.left 和 root.right；
2.翻转root.left 树的左右子树；
3.翻转root.right树的左右子树。

代码实现：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

6. 平衡二叉树

OJ链接

思路：
通过左右子树高度差来判断是否平衡：
先求当前 root 节点是不是平衡的；
再去判断左树是不是平衡的；
再去判断右树是不是平衡的。

代码实现：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(Math.abs(leftHeight - rightHeight) < 2 &&
        isBalanced(root.left) &&
        isBalanced(root.right)){
            return true;
        }else{
            return false;
        }
    }

    public int getHeight(TreeNode root){
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }
}

时间复杂度：O(N2)
求高度方法的时间复杂度为O(N)，而每一个节点都需要求高度，所以是 O(N2) 。

那么如果要求时间复杂度 O(N) 该怎么实现呢？
分析：
在以上代码执行到求左子树高度时，会一直往下递归求leftHeight和rightHeight，就算途中发现了leftHeight和rightHeight之差大于1（不符合平衡树），代码依然会继续执行，所以我们可以加一个判断条件：
代码实现：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return getHeight(root) >= 0;
    }

    public int getHeight(TreeNode root){
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
		int rightHeight = getHeight(root.right);
        if(leftHeight >= 0 && rightHeight >= 0 &&
            Math.abs(leftHeight - rightHeight) <= 1){
            return Math.max(leftHeight,rightHeight) + 1;
        }else{
            return -1;
        }
    }
}

7. 对称二叉树

OJ链接

思路：
判断 root 的左树和 root 的右树是否对称。
对称：判断左树的左和右树的右；左树的右和右树的左。

代码实现：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }

    private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree == null && rightTree != null || leftTree != null && rightTree == null){
            return false;
        }
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) &&
         isSymmetricChild(leftTree.right,rightTree.left);
    }
}

8. 二叉树构建及遍历

OJ链接

子问题思路：
代码实现：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
	// 定义内部类：
    static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inOrder(root);
        }
    }

    private static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val +" ");
        inOrder(root.right);
    }

    private static int i;
    private static TreeNode createTree(String str){
        if(str.charAt(i) != '#'){
        	// 前序顺序：
            TreeNode root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
            return root;
        }else{
            i++;
            return null;
        }
    }
}

9. 最近公共祖先

OJ链接

思路一：
如果每个节点有父亲节点的地址/关系，此时怎么做？
这是不是就是求链表的交点！！！
但是我们并没有父亲节点的地址，这时我们可以使用两个栈，分别从根节点开始入路径：
在这里插入图片描述在这里插入图片描述
之后就与求链表相交节点的方法类似了：
长的先走节点差值步数，然后同时走。
那么我们的问题就变成了：如何去存储根节点到p或者q路径上的所有节点？
递归！只要root不为空，就直接入栈；递到叶子结点后，若依然没找到目标节点就开始归，出栈。找到了就返回。（找路径时依然用到了子问题思路）

代码实现：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == null || q == null){
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root,p,stack1);

        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();

        if(size1 > size2){
            int size = size1 - size2;
            while(size > 0){
                stack1.pop();
                size--;
            }
        }else{
            int size = size2 - size1;
            while(size > 0){
                stack2.pop();
                size--;
            }
        }
        // 走到这里，两个栈中一定是相同的节点个数
        while(stack1.peek() != stack2.peek()){
            stack1.pop();
            stack2.pop();
        }
        return stack1.peek();
    }
    
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root == null || node == null){
            return false;
        }

        stack.push(root);

        if(root == node){
            return true;
        }

        boolean flg1 = getPath(root.left,node,stack);
        if(flg1 == true){
            return true;
        }

        boolean flg2 = getPath(root.right,node,stack);
        if(flg2 == true){
            return true;
        }

        stack.pop();

        return false;
    }
}

思路二：
我们先介绍一种树的类型：
二叉搜索树（二叉排序树）
在这里插入图片描述

特点：

  1. 左子树值都比根节点值小，右子树值都比根节点值大；
  2. 中序遍历是有序的。

两个节点有以下三种情况：
在这里插入图片描述

参考以上三种情况，本题也有如下三种情况：
在这里插入图片描述

代码实现：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == null || q == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null){
            return root;
        }else if(leftTree != null){
            return leftTree;
        }else if(rightTree != null){
            return rightTree;
        }else{
            return null;
        }
    }
}

10. 二叉搜索树与双向链表

OJ链接

注意要求：不能创建新节点，只能调整指向。
思路：
1.怎么有序？ ：中序遍历
2.二叉搜索树如何解决双向链表前驱和后继的问题？

代码实现：

public class Solution {

    private TreeNode prev;
  
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        convertChild(pRootOfTree);
        TreeNode head = pRootOfTree;
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
  
    private void convertChild(TreeNode pRootOfTree){
        if(pRootOfTree == null){
            return;
        }
        convertChild(pRootOfTree.left);
        pRootOfTree.left = prev;
        if(prev != null){
            prev.right = pRootOfTree;
        }
        prev = pRootOfTree;
        convertChild(pRootOfTree.right);
    }
}

11. 从前序与中序遍历序列构造二叉树

OJ链接

思路：
1.遍历：前序遍历的数组，i下标开始遍历；
2.当拿到前序遍历的一个字符之后，在中序遍历的区间范围内，找到这个根节点 rootindex；
3.rootindex左边就是根的左树，右边就是根的右树。

代码实现：

class Solution {

    public int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
        // 判断当前节点是否还有左子树或者右子树
        if(inbegin > inend){
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex]); 

        // 找到root在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        preIndex++;

        if(rootIndex == -1){
            return null;
        }

        // 构建左子树和右子树
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int val){
        for(int i = inbegin;i <= inend; i++){
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }
}

12. 从中序与后序遍历序列构造二叉树

OJ链接

上题修改一下即可。

代码实现：

class Solution {

    public int postIndex = 0;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }
    
    private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
        // 判断当前节点是否还有左子树或者右子树
        if(inbegin > inend){
            return null;
        }

        TreeNode root = new TreeNode(postorder[postIndex]); 

        // 找到root在中序遍历的位置
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;

        if(rootIndex == -1){
            return null;
        }

        // 构建左子树和右子树
        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);

        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int val){
        for(int i = inbegin;i <= inend; i++){
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }
}

13. 根据二叉树创建字符串

OJ链接

画图一步步分析。

代码实现：

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();

        tree2strChild(root,stringBuilder);

        return stringBuilder.toString();
    }

    private void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if(root == null){
            return;
        }
        stringBuilder.append(root.val);

        if(root.left != null){
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(root.right == null){
                return;
            }else{
                stringBuilder.append("()");
            }
        }

        if(root.right == null){
            return;
        }else{
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }
    }
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/93267.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！