【算法】TOP101-二叉树篇(持续更新ing)

xxxflower

发布于 2023-10-23 18:58:22

1350

发布于 2023-10-23 18:58:22

文章被收录于专栏：《数据结构》

1. JZ36 二叉搜索树与双向链表

解题思路: 由题目可知,这是一颗二叉搜索树.二叉搜索树的特点就是他的中序遍历是有序的.所以本题我们大的框架就是要在中序遍历里完成.具体解题如下:

代码:

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        TreeNode head = pRootOfTree;
        convertChild(head);
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
    public static TreeNode prev = null;
    public static void convertChild(TreeNode pCur){
        if(pCur == null){return;}
        convertChild(pCur.left);
        pCur.left = prev;
        if(prev != null){prev.right = pCur;}
        prev = pCur;
        convertChild(pCur.right);
    }
}

2. 100. 相同的树

解题思路: 要想判断两颗二叉树是否相同,那么就要从两个方面去考虑:

二叉树的结构
二叉树的值

本题我们采用递归的思想,则代码如下:

/**
 * 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);
    }
}

3. 572. 另一棵树的子树

解题思路: 想要判断一棵树是不是另一颗树的子树,我们可以采用递归的思想.先判断子树是不是这棵树的左树,在判断是不是这棵树的右树.要是都不是,则这棵子树不是树的子树.则有以下代码:

/**
 * 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 root, TreeNode subRoot) {
        if(root== null){
            return false;
        }
        if(isSameTree(root,subRoot)){return true;}
        if(isSameTree(root.left,subRoot)){return true;}
        if(isSameTree(root.right,subRoot)){return true;}
        return false;
    }
    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);
    }
}

4. BM26 求二叉树的层序遍历

解题思路:

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        //先创建一个ListList列表用来存放
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            ArrayList<Integer> tmp = new ArrayList<>();
            while(size > 0){
                TreeNode cur = qu.poll();
                size--;
                tmp.add(cur.val);
                if(cur.left != null){
                    qu.offer(cur.left);
                }
                if(cur.right != null){
                    qu.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-10-18，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树