1898 2018-12-01 2020-06-25

前言：牛客网剑指Offer编程题55~60题。

一、链表中环的入口结点

1、题目描述

考点链表，给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

2、我的代码

        public ListNode EntryNodeOfLoop(ListNode pHead) {
            ArrayList<ListNode> list = new ArrayList<>();
            while (pHead != null) {
                if (list.contains(pHead)) {
                    return pHead;
                }
                list.add(pHead);
                pHead = pHead.next;
            }
            return null;
        }

3、别人的代码

还是看下大神的代码吧，心累啊。

第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口
public class Solution { 
    ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead == null || pHead.next == null)
            return null;
        ListNode p1 = pHead;
        ListNode p2 = pHead;
        while(p2 != null && p2.next != null ){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2){
                p2 = pHead;
                while(p1 != p2){
                    p1 = p1.next;
                    p2 = p2.next;
                }
                if(p1 == p2)
                    return p1;
            }
        }
        return null;
    }
}

二、删除链表中重复的结点

1、题目描述

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

2、我的代码

一看到这题，我就想到了LinkedHashMap，哈哈，不能这么搞。

public ListNode deleteDuplication(ListNode pHead) {
    if (pHead == null) {
        return null;
    }
    ListNode head = new ListNode(0);
    ListNode root = head;
    ListNode cur = pHead;
    ListNode nex = cur.next;
    boolean isInCheck = false;
    while (nex != null) {
        if (cur.val != nex.val) {
            if (!isInCheck) {
                System.out.println(head.val + "正常添加" + cur.val);
                head.next = cur;
                head = head.next;
                cur = cur.next;
                nex = nex.next;
                head.next = null;
            } else {
                cur = nex;
                nex = nex.next;
                isInCheck = false;
            }
        } else {
            isInCheck = true;
            nex = nex.next;
        }
    }
    if (cur.next == null && !isInCheck) {
        head.next = cur;
    }
    return root.next;
}

三、二叉树的下一个结点

1、题目描述

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

2、我的代码

static class FiftySeven {
    public static class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
        TreeLinkNode(int val) {
            this.val = val;
        }
    }

    boolean findTarget = false;
    TreeLinkNode target = null;

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        TreeLinkNode node = pNode;
        while (pNode.next != null) {
            pNode = pNode.next;
        }
        TreeLinkNode root = pNode;
        traverse(root, node);
        return target;
    }

    private void traverse(TreeLinkNode root, TreeLinkNode node) {
        if (root == null || target != null) {
            return;
        }
        traverse(root.left, node);
        if (findTarget) {
            target = root;
            findTarget = false;
        }
        if (root == node) {
            findTarget = true;
        }
        traverse(root.right, node);
    }

    private static void test() {
        TreeLinkNode node1 = new TreeLinkNode(8);
        TreeLinkNode node2 = new TreeLinkNode(6);
        TreeLinkNode node3 = new TreeLinkNode(10);
        TreeLinkNode node4 = new TreeLinkNode(5);
        TreeLinkNode node5 = new TreeLinkNode(7);
        TreeLinkNode node6 = new TreeLinkNode(9);
        TreeLinkNode node7 = new TreeLinkNode(11);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println(new FiftySeven().GetNext(node1).val);
    }
}

四、对称的二叉树

1、题目描述

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

2、我的代码

public static class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null) {
        return true;
    }
    ArrayList<TreeNode> list = new ArrayList<>();
    traverse(pRoot, list);
    if (list.size() % 2 == 0 || list.get(list.size() / 2) != pRoot) {
        return false;
    }
    while (list.size() != 1) {
        if (list.remove(0).val != (list.remove(list.size() - 1).val)) {
            return false;
        }
    }
    return true;
}

private void traverse(TreeNode node, ArrayList<TreeNode> list) {
    if (node.left != null) {
        traverse(node.left, list);
    }
    System.out.println(node.val);
    list.add(node);
    if (node.right != null) {
        traverse(node.right, list);
    }
}

哈哈，答案错误：您提交的程序没有通过所有的测试用例，case通过率为90.00%。第一次觉得，完全通过一次测试，也不容易啊。

3、别人的代码

别人的代码就是好--系列博客，哈哈。

boolean isSymmetrical1(TreeNode pRoot) {
    if (pRoot == null) {
        return true;
    }
    return isSymmetrical1(pRoot.left, pRoot.right);
}

boolean isSymmetrical1(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) {
        return true;
    }
    if (t1 != null && t2 != null) {
        return t1.val == t2.val && isSymmetrical1(t1.left, t2.right) && isSymmetrical1(t1.right, t2.left);
    }
    return false;
}

4、别人的代码2

膜拜吧，凡人。

boolean isSymmetricalDFS(TreeNode pRoot) {
    if (pRoot == null) return true;
    Stack<TreeNode> s = new Stack<>();
    s.push(pRoot.left);
    s.push(pRoot.right);
    while (!s.empty()) {
        TreeNode right = s.pop();//成对取出
        TreeNode left = s.pop();
        if (left == null && right == null) continue;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        //成对插入
        s.push(left.left);
        s.push(right.right);
        s.push(left.right);
        s.push(right.left);
    }
    return true;
}

boolean isSymmetricalBFS(TreeNode pRoot) {
    if (pRoot == null) return true;
    Queue<TreeNode> s = new LinkedList<>();
    s.offer(pRoot.left);
    s.offer(pRoot.right);
    while (!s.isEmpty()) {
        TreeNode right = s.poll();//成对取出
        TreeNode left = s.poll();
        if (left == null && right == null) continue;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        //成对插入
        s.offer(left.left);
        s.offer(right.right);
        s.offer(left.right);
        s.offer(right.left);
    }
    return true;
}

五、按之字形顺序打印二叉树

1、题目描述

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

2、别人的代码

自己有点没思路，索性直接看别人的代码了。

public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    int layer = 1;
    //s1存奇数层节点
    Stack<TreeNode> s1 = new Stack<TreeNode>();
    s1.push(pRoot);
    //s2存偶数层节点
    Stack<TreeNode> s2 = new Stack<TreeNode>();

    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

    while (!s1.empty() || !s2.empty()) {
        if (layer%2 != 0) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            while (!s1.empty()) {
                TreeNode node = s1.pop();
                if(node != null) {
                    temp.add(node.val);
                    System.out.print(node.val + " ");
                    s2.push(node.left);
                    s2.push(node.right);
                }
            }
            if (!temp.isEmpty()) {
                list.add(temp);
                layer++;
                System.out.println();
            }
        } else {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            while (!s2.empty()) {
                TreeNode node = s2.pop();
                if(node != null) {
                    temp.add(node.val);
                    System.out.print(node.val + " ");
                    s1.push(node.right);
                    s1.push(node.left);
                }
            }
            if (!temp.isEmpty()) {
                list.add(temp);
                layer++;
                System.out.println();
            }
        }
    }
    return list;
}

写得真是好啊。

3、别人的代码2

思路也是不错的。

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    if (pRoot == null) {
        return ret;
    }
    ArrayList<Integer> list = new ArrayList<>();
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.addLast(null);//层分隔符
    queue.addLast(pRoot);
    boolean leftToRight = true;
     
    while (queue.size() != 1) {
        TreeNode node = queue.removeFirst();
        if (node == null) {//到达层分隔符
            Iterator<TreeNode> iter = null;
            if (leftToRight) {
                iter = queue.iterator();//从前往后遍历
            } else {
                iter = queue.descendingIterator();//从后往前遍历
            }
            leftToRight = !leftToRight;
            while (iter.hasNext()) {
                TreeNode temp = (TreeNode)iter.next();
                list.add(temp.val);
            }
            ret.add(new ArrayList<Integer>(list));
            list.clear();
            queue.addLast(null);//添加层分隔符
            continue;//一定要continue
        }
        if (node.left != null) {
            queue.addLast(node.left);
        }
        if (node.right != null) {
            queue.addLast(node.right);
        }
    }     
    return ret;
}

六、把二叉树打印成多行

1、题目描述

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

2、别人的代码

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        depth(pRoot, 1, list);
        return list;
    }
     
    private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list){
        if(root == null) return;
        if(depth > list.size())
            list.add(new ArrayList<Integer>());
        list.get(depth -1).add(root.val);
         
        depth(root.left, depth + 1, list);
        depth(root.right, depth + 1, list);
    }
}

3、别人的代码2

ArrayList> Print(TreeNode pRoot) {
    //存放结果
    ArrayList> arrayLists = new ArrayList();
    if (pRoot == null) {
        return arrayLists;
    }
    //使用队列，先进先出
    Queue queue = new LinkedList();
    //存放每行的列表
    ArrayList arrayList = new ArrayList();
    //记录本层打印了多少个
    int start = 0;
    //记录下层打几个
    int end = 1;
    queue.add(pRoot);
    while (!queue.isEmpty()) {
        TreeNode temp = queue.remove();
        //添加到本行的arrayList
        arrayList.add(temp.val);
        start++;
        //每打印一个节点，就把此节点的下一层的左右节点加入队列，并记录下一层要打印的个数
        if (temp.left != null) {
            queue.add(temp.left);
        }
        if (temp.right != null) {
            queue.add(temp.right);
        }
        //判断本层打印是否完成
        if (start == end) {
            //此时的queue中存储的都是下一层的节点，则end即为queue大小
            end = queue.size();
            start = 0;
            //把arrayList添加到结果列表arrayLists中
            arrayLists.add(arrayList);
            //重置arrayList
            arrayList = new ArrayList();
        }
    }
    return arrayLists;
}

稍稍有点急，稳住吧，还有最后一篇。

总访问次数: 271次, 一般般帅 创建于 2018-12-01, 最后更新于 2020-06-25