剑指Offer面试题思路解析

r囧r小猫 2022-05-27 11:52 189阅读 0赞

> 面试题58：二叉树的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。  
**思路分析：**  
1.如果二叉树为空，返回空  
2.如果二叉树的右子树不为空，那么返回右子树的最左孩子节点  
3.如果二叉树的右子树为空，那么寻找第一个节点是父节点左孩子的节点，返回其父节点，既是当前节点的下一个节点。

public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if(pNode == null)
                return pNode;
            if(pNode.right != null){
                TreeLinkNode curr = pNode.right;
                while(curr != null && curr.left!= null){
                    curr = curr.left;
                }
                return curr;
            }else{
                TreeLinkNode curr = pNode;
                while(curr.next != null){
                    if(curr.next.left == curr)
                        return curr.next;
                    curr = curr.next;
                }
            }
            return null;
        }

> 面试题59： 对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。  
**思路分析：**  
对于二叉树的遍历，针对前序遍历定义一种对称的遍历算法，即先遍历父节点，再遍历它的右子节点，最后遍历它的左子节点。  
如果是二叉树是对称的，那么前序遍历的结果和我们自定义的遍历算法得到的结果是一致的。  
也就是左子树的左子树和右子树的右子树相同，且左子树的右子树和右子树的左子树相同！  
*注意：要考虑到把空节点也加入考虑，否则如果一棵树的所有节点值均相同，但是并不是对称的，只有通过空节点加以辨别*

> 递归实现：

boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot == null)
                return true;
            return symmetricalCore(pRoot,pRoot);
        }
        boolean symmetricalCore(TreeNode p1,TreeNode p2){
        //都为空节点，
            if(p1 == null && p2 == null)
                return true;
            if(p1 == null || p2 == null)
                return false;
            if(p1.val != p2.val)
                return false;
            return symmetricalCore(p1.left,p2.right) && symmetricalCore(p1.right,p2.left);
        }

非递归实现：  
需要借助两个栈来实现，分别存放右子树和左子树的节点，左子树入栈左、右孩子节点，右子树入栈右、左孩子节点，然后依次出栈判断节点是否相同

boolean isSymmetrical(TreeNode pRoot){
            if(pRoot == null)
                return true;
            Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();
            s1.push(pRoot.left);
            s2.push(pRoot.right);
            while(!s1.empty() && !s2.empty()){
                TreeNode left = s1.pop();
                TreeNode right = s2.pop();
                if(left == null && right == null)
                    continue;
                if(left == null || right == null)
                    return false;
                if(left.val == right.val){
                    s1.push(left.left);
                    s1.push(left.right);
                    s2.push(right.right);
                    s2.push(right.left);
                }else{
                    return false;
                }
            }
            return true;
        }

> 面试题62：按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。  
**思路分析：**  
奇数层是从左到右打印节点，偶数层是从右到左打印节点，奇数层和偶数层打印的节点顺序是不一致的，所以我们需要两个栈来分别保存奇数层的节点和偶数层的节点。  
打印顺序的不同在于节点入栈的顺序不同，奇数层的是其左、右节点入栈，偶数层是其右、左节点入栈。所以需要一个变量来记录当前是树的哪一层，从而判断是奇数层还是偶数层。

import java.util.ArrayList;
    import java.util.Stack;
    /*
    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) {
            //保存奇数层节点
            Stack<TreeNode> s1 = new Stack<>();
            //保存偶数层节点
            Stack<TreeNode> s2 = new Stack<>();
            ArrayList<Integer> curr;
            ArrayList<ArrayList<Integer>> result = new ArrayList<>();
            if(pRoot == null)
                return result;
            int level = 1;
            s1.push(pRoot);
            while(!s1.empty() || !s2.empty()){
                curr = new ArrayList<>();
                if(level % 2 == 1){
                    while(!s1.empty()){
                        TreeNode pNode = s1.pop();
                        curr.add(pNode.val);
                        if(pNode.left != null)
                            s2.push(pNode.left);
                        if(pNode.right != null)
                            s2.push(pNode.right);
                    }
                    if(!curr.isEmpty()){
                        level++;
                        result.add(curr);
                    }
                }else{
                    while(!s2.empty()){
                        TreeNode pNode = s2.pop();
                        curr.add(pNode.val);
                        if(pNode.right != null)
                            s1.push(pNode.right);
                        if(pNode.left != null)
                            s1.push(pNode.left);
                    }
                    if(!curr.isEmpty()){
                        level++;
                        result.add(curr);
                    }
                }
            }
            return result;
        }
    }

> 面试题60：把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。  
**思路：**  
按层打印，需要队列保存节点，每一层输出一行，所以需要记录当前打印层的节点数，每次出对列便把当前打印层的节点数-1，在入队列的时候我们可以计算出下一层的节点数。

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 {
        ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> result = new ArrayList<>();
            if(pRoot == null)
                return result;
            Queue<TreeNode> s = new LinkedList<>();
            int currLevel = 1;
            int nextLevel = 0;
            s.offer(pRoot);
            ArrayList<Integer> curr = new ArrayList<>();
            while(!s.isEmpty()){
                TreeNode pNode = s.poll();
                currLevel--;
                curr.add(pNode.val);
                if(pNode.left != null){
                    s.offer(pNode.left);
                    nextLevel++;
                }
                if(pNode.right != null){
                    s.offer(pNode.right);
                    nextLevel++;
                }
                if(currLevel == 0){
                    result.add(curr);
                    curr = new ArrayList<>();
                    currLevel = nextLevel;
                    nextLevel = 0;
                }
            }
            return result;
        }
    
    }

递归实现：

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);
        }
    }

> 面试题62：序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树  
**思路分析：**  
正常情况下我们需要知道前序遍历、中序遍历或者中序遍历，后续遍历才能构建出二叉树，但是在这里，如果把空节点也保存下来，那么我们就能通过这个包含了空节点的序列构造出二叉树  
此处利用了前序遍历

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        String Serialize(TreeNode root) {
            StringBuffer sb = new StringBuffer();
            if(root == null){
                sb.append("#,");
                return sb.toString();
            }
            sb.append(root.val+",");
            sb.append(Serialize(root.left));
            sb.append(Serialize(root.right));
            return sb.toString();
        }
        private int index =  -1;
        TreeNode Deserialize(String str) {
            index ++;
            String[] strs = str.split(",");
            TreeNode node = null;
            if(!strs[index].equals("#")){
                node = new TreeNode(Integer.parseInt(strs[index]));
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            }
            return node;
        }
    }

> 面试题63：二叉搜索树的第K个结点

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \\ 3 7 /\\ /\\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。  
**思路：**  
中序遍历二叉树即可得到一个有序序列，所有中序遍历二叉树，第K大的结点就是第K次访问的结点，可以使用递归或者非递归方式实现

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 { 
        //非递归实现，借助栈来实现
        TreeNode KthNode(TreeNode pRoot, int k){
            int index = 0;
            Stack<TreeNode> s = new Stack<>();
            if(pRoot == null)
                return pRoot;
            while(pRoot != null || !s.empty()){
                while(pRoot != null){
                    s.push(pRoot);
                    pRoot = pRoot.left;
                }
                if(!s.empty()){
                    TreeNode p = s.pop();
                    index++;
                    if(index == k)
                        return p;
                    pRoot = p.right;
                }
            }
            return null;
        }
        //递归实现
        private int index = 0;
        TreeNode KthNode(TreeNode pRoot, int k)
        {
            if(pRoot != null){
                TreeNode p1 = KthNode(pRoot.left,k);
                if(p1 != null)
                    return p1;
                index ++;
                if(index == k)
                    return pRoot;
                TreeNode p2 = KthNode(pRoot.right,k);
                if(p2 != null)
                    return p2;
            }
            return null;
        }
    }

> 面试题64：数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。  
**思路分析：**  
为了保证插入新数据和取中位数的时间效率都高效，这里使用大顶堆+小顶堆的容器，并且满足：  
1、两个堆中的数据数目差不能超过1，这样可以使中位数只会出现在两个堆的交接处；  
2、大顶堆的所有数据都小于小顶堆，这样就满足了排序要求。

//Java的PriorityQueue 是从JDK1.5开始提供的新的数据结构接口
    //默认内部是自然排序，结果为小顶堆
    //可以自定义排序器,比如下面反转比较，完成大顶堆。
    import java.util.*;
    public class Solution { 
        int count = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //默认最小堆
                return o2.compareTo(o1);
            }
        });
        public void Insert(Integer num) {
            count++;
            if((count & 1) == 0){   //偶数
                if(!maxHeap.isEmpty() && num < maxHeap.peek()){
                    maxHeap.offer(num);
                    num = maxHeap.poll();
                }
                minHeap.offer(num);
            }else{
                if(!minHeap.isEmpty() && num > minHeap.peek()){
                    minHeap.offer(num);
                    num = minHeap.poll();
                }
                maxHeap.offer(num);
            }
    
        }
    
        public Double GetMedian() {
            double result = 0.0;
            if((count & 1) == 1){
                result = (double) maxHeap.peek();
            }else{
                result = (maxHeap.peek()+minHeap.peek())/2.0;
            }
            return result;
        }
    }

> 面试题65：滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。  
**思路分析：**  
滑动窗口应当是队列，但为了得到滑动窗口的最大值，队列序可以从两端删除元素，因此使用双端队列。其中队列中存储的是元素在数组中索引位置而非元素本身！  
原则：对新来的元素k，将其与双端队列中的元素相比较  
1）前面比k小的，直接移出队列（因为不再可能成为后面滑动窗口的最大值了!）,  
2）前面比k大的X，比较两者下标，判断X是否已不在窗口之内，不在了，直接移出队列  
其中，队列的第一个元素是滑动窗口中的最大值

import java.util.*;
    public class Solution {
        public ArrayList<Integer> maxInWindows(int [] num, int size)
        {
            LinkedList<Integer> q = new LinkedList<Integer>();
            ArrayList<Integer> result = new ArrayList<>();
            if(num == null || size > num.length || size <= 0)
                return result;
            for(int i=0;i<size-1;i++){
                while(!q.isEmpty() && num[i] > num[q.getLast()]){
                    q.removeLast();
                }
                q.addLast(i);
            }
            for(int i=size-1;i<num.length;i++){
                while(!q.isEmpty() && num[i] > num[q.getLast()]){
                    q.removeLast();
                }
                q.addLast(i);
                if(i - q.getFirst()+1 >size)
                    q.removeFirst();
                result.add(num[q.getFirst()]);
            }
            return result;
        }
    }