【算法】TOP101

算法】TOP101"/>

【算法】TOP101

文章目录

• 1. JZ36 二叉搜索树与双向链表
• 2. 100. 相同的树
• 3. 572. 另一棵树的子树
• 4. BM26 求二叉树的层序遍历

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

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. 相同的树

100. 相同的树

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

1. 二叉树的结构
2. 二叉树的值

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

/*** 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. 另一棵树的子树

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 求二叉树的层序遍历

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;}
}