1. JZ36 二叉搜索树与双向链表
解题思路: 由题目可知,这是一颗二叉搜索树.二叉搜索树的特点就是他的中序遍历是有序的.所以本题我们大的框架就是要在中序遍历里完成.具体解题如下:
代码:
代码语言：javascript复制/**
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. 相同的树
解题思路: 要想判断两颗二叉树是否相同,那么就要从两个方面去考虑:
- 二叉树的结构
- 二叉树的值
本题我们采用递归的思想,则代码如下:
代码语言：javascript复制/**
* 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. 另一棵树的子树
解题思路: 想要判断一棵树是不是另一颗树的子树,我们可以采用递归的思想.先判断子树是不是这棵树的左树,在判断是不是这棵树的右树.要是都不是,则这棵子树不是树的子树.则有以下代码:
代码语言：javascript复制/**
* 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;
}
}
