将二叉树原地转为双向链表
class Solution {
//定义头节点与尾节点
Node pre,head;
public Node treeToDoublyList(Node root) {
if(root==null){
return null;
}
dfs(root);
//最终head指向头节点,pre指向尾节点
head.left=pre;
pre.right=head;
return head;
}
public void dfs(Node root){
if(root==null){
return;
}
dfs(root.left);
if(pre==null){
//头节点
head=root;
}else{
pre.right=root;
}
root.left=pre;
pre=root;
dfs(root.right);
}
}
二叉树的序列化与反序列化
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
String s=dfs(root,"");
return s;
}
public String dfs(TreeNode root,String s){
if(root==null){
s+="None,";
return s;
}
//将当前节点加入
s+=String.valueOf(root.val)+",";
s=dfs(root.left,s);
s=dfs(root.right,s);
return s;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
//将对应的序列化字符串预处理
String[] list=data.split(",");
List<String> datalist=new ArrayList<String>(Arrays.asList(list));
//List<String> datalist=new ArrayList<String>(Arrays.asList(list));
TreeNode res=handler(datalist);
return res;
}
public TreeNode handler(List<String> list){
if(list.get(0).equals("None")){
list.remove(0);
return null;
}
TreeNode root=new TreeNode(Integer.valueOf(list.get(0)));
list.remove(0);
root.left=handler(list);
root.right=handler(list);
return root;
}
}
通过先序遍历与后序遍历序列构造二叉树
class Solution {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
int n=preorder.length;
if(n==0){
return null;
}
TreeNode root=new TreeNode(preorder[0]);
if(n==1){
return root;
}
int L=0;
for(int i=0;i<postorder.length;i++){
if(postorder[i]==preorder[1]){
L=i+1;
break;
}
}
//通过递归的方式
root.left=constructFromPrePost(Arrays.copyOfRange(preorder,1,L+1),Arrays.copyOfRange(postorder,0,L));
root.right=constructFromPrePost(Arrays.copyOfRange(preorder,L+1,n),Arrays.copyOfRange(postorder,L,n-1));
return root;
}
}
通过广度优先的方式判断完全二叉树
class Solution {
public boolean isCompleteTree(TreeNode root) {
//通过广度优先的方式判断
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
boolean flag=false;
while(!queue.isEmpty()){
TreeNode node=queue.poll();
if((flag&&(node.left!=null||node.right!=null))||(node.left==null&&node.right!=null)){//不可能出现左子树为空,右子树非空的情况;前面的判断条件对应的flag结点之后的所有的节点都是叶子节点
return false;
}
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
if(node.left==null||node.right==null){
flag=true;
}
}
return true;
}
}
方式二,通过节点编号的方式判断
最后一个节点的编号等于结点的数量;通过广度优先的方式
class Solution {
public boolean isCompleteTree(TreeNode root) {
List<Node> nums=new ArrayList<Node>();
Queue<Node> queue=new LinkedList<Node>();
queue.offer(new Node(root,1));
while(!queue.isEmpty()){
Node node=queue.poll();
nums.add(node);
if(node.node.left!=null){
queue.offer(new Node(node.node.left,node.id*2));
}
if(node.node.right!=null){
queue.offer(new Node(node.node.right,node.id*2+1));
}
}
return nums.get(nums.size()-1).id==nums.size();
}
}
class Node{
TreeNode node;
int id;
public Node(TreeNode node,int id){
this.node=node;
this.id=id;
}
}