算法】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. 相同的树
解题思路:
要想判断两颗二叉树是否相同,那么就要从两个方面去考虑:
- 二叉树的结构
- 二叉树的值
本题我们采用递归的思想,则代码如下:
/*** 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;}
}
更多推荐
【算法】TOP101
发布评论