剑指offer（51-60）题解（二）

2022-11-09 91

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

公共DNS（含HTTPDNS解析），每月1000万次HTTP解析

云解析 DNS，旗舰版 1个月

全局流量管理 GTM，标准版 1个月

简介： 剑指offer（51-60）题解

56题解–删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路解析

这里我还是先将所有的节点的值存储下来，暂时不存储他们的next指针，在这个过程中找到所有的节点以及重复的节点，之后再将这些重复的节点筛选过后将他们重新存入一个list之中，并且将他们重新串起来便可。

源代码

/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.ArrayList;
import java.util.List;
public class Solution {
  public ListNode deleteDuplication(ListNode pHead)
  {
     //存取所有的节点的值
     List<Integer>list1=new ArrayList<Integer>();
     //存取重复的节点的值
     List<Integer>list2=new ArrayList<Integer>();
     //存取删除重复节点的链表
     List<ListNode>list3=new ArrayList<ListNode>();
     while(pHead!=null) 
     {
       int node=pHead.val;
       if(!list1.contains(node))
         list1.add(node);
       else 
         list2.add(node);
       if(pHead.next!=null)
         pHead=pHead.next;
       else 
         break;
     }
     for(int i=0;i<list1.size();i++)
     {
       if(!list2.contains(list1.get(i)))
       {
         ListNode node=new ListNode(list1.get(i));
         list3.add(node);
       }
     }
     if(list3.size()==0)
       return null;
     else 
     {
       for(int i=0;i<list3.size()-1;i++)
         list3.get(i).next=list3.get(i+1);
       return list3.get(0);
    }
  }
}

57题解–二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路解析

这题不一样的地方就是他给的节点并不一定就是根节点，所以我们需要先循环找到根节点，之后将它的中序比那里序列保存下来，一一对比输出他的next节点即可。注意的是我们一开始寻找根节点切不可直接用他给的节点寻找，否则之后寻找该节点的next节点时，因为该节点已经发生改变，所以我们是无法找到该节点的。

源代码

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;
    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.ArrayList;
public class Solution {
 ArrayList<TreeLinkNode>list=new ArrayList<TreeLinkNode>();
  //中序遍历序列
  public void Print(TreeLinkNode pNode)
    {
    if(pNode.left!=null)
      Print(pNode.left);
        list.add(pNode);
        if(pNode.right!=null)
          Print(pNode.right);
    }
  public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
    TreeLinkNode node=new TreeLinkNode(pNode.val);
    if(pNode.left!=null)
      node.left=pNode.left;
    if(pNode.right!=null)
      node.right=pNode.right;
    //说明当前节点不是根节点
    if(pNode.next!=null)
    {
      node.next=pNode.next;
      while(node.next!=null)
      {
        node=node.next;
      }
    }
    //当前节点已经是根节点
        Print(node);
        for(int i=0;i<list.size()-1;i++)
        {
          if(list.get(i).val==pNode.val)
            return list.get(i+1);
        }
        return null;
    }
}

58题解–对称的二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路解析

这里我们首先需要理解对称的定义

通过上述的图，我们大致可以得出二叉树对称的条件有：

node.left.val=node.right.val

node.left.right.val=node.right.left.val

node.left.left.val=node.right.right.val

源代码

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public boolean jude(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        } else if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        } else {
            return jude(node1.left, node2.right) && jude(node1.right, node2.left);
        }
    }
    public boolean isSymmetrical(TreeNode pRoot) {
        return pRoot==null || jude(pRoot.left, pRoot.right);
    }
}

59题解–按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路解析

其实这题本质上与之前一条打印二叉树的题是一样的们只不过他这里需要让我们之字形遍历，就是说有的list我们需要将他们倒转之后再输出。

之前我们的思路是这样：

现在我们只不过多加了一步：

源代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>>list=new ArrayList<ArrayList<Integer>>();
    int count=0;
        Queue<TreeNode> queue1=new LinkedList<TreeNode>();
        Queue<TreeNode> queue2=new LinkedList<TreeNode>();
        if(pRoot==null)
          return list;
        queue2.add(pRoot);
        while(!queue2.isEmpty())
        {   
          count++;
          ArrayList<Integer>list1=new ArrayList<Integer>();
          for(TreeNode node:queue2)
          {
            queue1.add(node);
            list1.add(node.val);
          }
          if(count%2==0)
          {
            ArrayList<Integer>list2=new ArrayList<Integer>();
            for(int i=list1.size()-1;i>-1;i--)
              list2.add(list1.get(i));
            list.add(list2);
          }
          else 
            list.add(list1);
          queue2.clear();
          for(TreeNode node:queue1)
          {
            if(node.left!=null)
              queue2.add(node.left);
            if(node.right!=null)
              queue2.add(node.right);
          }
          queue1.clear();
        }
    return list;
    }
}

60题解–把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路解析

这题本质上还是和之前的打印二叉树一样，换汤不换药

在这里插入图片描述

源代码

import java.util.ArrayList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
   ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>>list=new ArrayList<ArrayList<Integer>>();
    int count=0;
        Queue<TreeNode> queue1=new LinkedList<TreeNode>();
        Queue<TreeNode> queue2=new LinkedList<TreeNode>();
        if(pRoot==null)
          return list;
        queue2.add(pRoot);
        while(!queue2.isEmpty())
        {   
          count++;
          ArrayList<Integer>list1=new ArrayList<Integer>();
          for(TreeNode node:queue2)
          {
            queue1.add(node);
            list1.add(node.val);
          }
          list.add(list1);
          queue2.clear();
          for(TreeNode node:queue1)
          {
            if(node.left!=null)
              queue2.add(node.left);
            if(node.right!=null)
              queue2.add(node.right);
          }
          queue1.clear();
        }
    return list;
  }
}