15.深度优先搜索

一.二叉树的深度
1.题目描述：
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

2.示例：
例如：

给定二叉树 [3,9,20,null,null,15,7]，
图片说明
返回它的最大深度 3 。

3.解:
（1）我的答案：

class Solution {
    private HashMap<TreeNode,Integer> heighSet = new HashMap<>();

    public int maxDepth(TreeNode root) {
        getHeigh(root);
        return heighSet.getOrDefault(root,0);
    }

    private void getHeigh(TreeNode root){
        if (root == null) return;
        getHeigh(root.left);
        getHeigh(root.right);
        heighSet.put(root,Math.max(heighSet.getOrDefault(root.left,0),heighSet.getOrDefault(root.right,0))+1);
    }
}

（2）网友答案：

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                if (temp.left != null) queue.offer(temp.left);
                if (temp.right != null) queue.offer(temp.right);
            }
            res++;
        }
        return res;
    }
}

4.总结
二叉树中的深度优先搜索就是后序遍历,网友的方法是按层遍历的，不是递归，看懂代码即可，很巧妙，利用了队列这个数据结构。面试的时候很可能不让用递归的方法，所以学会这个方法很有用。

二.平衡二叉树
1.题目描述：
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

2.示例：
示例 1:

给定二叉树 [3,9,20,null,null,15,7]
图片说明
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]
图片说明
返回 false 。

3.解:
（1）我的答案：

class Solution {
    private HashMap<TreeNode,Integer> heighSet = new HashMap<>();

    public boolean isBalanced(TreeNode root) {
        return getHeigh(root);
    }

    private boolean getHeigh(TreeNode root){
        if (root == null) return true;
        boolean left = getHeigh(root.left);
        boolean right = getHeigh(root.right);
        heighSet.put(root,Math.max(heighSet.getOrDefault(root.left,0),heighSet.getOrDefault(root.right,0))+1);
        if (Math.abs(heighSet.getOrDefault(root.left,0)-heighSet.getOrDefault(root.right,0))>1) {
            return false;
        }
        return left && right;
    }
}

4.总结
没什么可说的

三.单词转换

1.题目描述：
给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词，但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。

编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个

2.示例：
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
["hit","hot","dot","lot","log","cog"]

3.解:
（1）我的答案：

    HashSet<String> history = new HashSet<>();//在深度遍历过程中记录下走过的节点
    List<String> res = new ArrayList<>();//最终要返回的结果

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)) return res;
        if (finish(beginWord, endWord, wordList)) res.add(0, beginWord);
        return res;
    }

    public boolean finish(String beginWord, String endWord, List<String> wordList) {
        //边界条件
        if (beginWord.equals(endWord)) return true; 
        if (history.contains(beginWord)) return false;
        history.add(beginWord);//将当前节点标记为已经过

        //回溯的核心
        for (int i = wordList.size() - 1; i >= 0; i--) {
            if (near(beginWord, wordList.get(i))) {
                //先添加再判断得到的是正序的res，先判断再添加得到的是逆序的，还得倒一下，麻烦
                res.add(wordList.get(i)); 
                if (finish(wordList.get(i), endWord, wordList)) return true;
                res.remove(res.size() - 1);
            }
        }
        return false;
    }

    public boolean near(String cur, String target) {
        int notSeemCount = 0; 
        for (int i = 0; i < cur.length(); i++) {
            if (cur.charAt(i) != target.charAt(i)) notSeemCount++;
        }
        return notSeemCount==1;
    }
}

（2）网友答案：

class Solution {

    HashSet<String> history = new HashSet<>();
    List<String> res = new ArrayList<>();

    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)) return res;
        if (finish(beginWord, endWord, wordList)) {
            res.add(0, beginWord);
        }
        return res;
    }

    public boolean finish(String beginWord, String endWord, List<String> wordList) {

        if (beginWord.equals(endWord)) return true; 
        if (history.contains(beginWord)) return false;

        for (int i = wordList.size() - 1; i >= 0; i--) {
            String temp = wordList.get(i);
            if (near(beginWord, temp)) {
                wordList.remove(i);
                res.add(temp); 
                if (finish(temp, endWord, wordList)) return true;
                res.remove(res.size() - 1);
                wordList.add(temp);
                history.add(temp);  
            }
        }
        return false;
    }

    public boolean near(String cur, String target) {
        int notSeemCount = 0; 
        for (int i = 0; i < cur.length(); i++) {
            if (cur.charAt(i) != target.charAt(i)) notSeemCount++;
        }
        return notSeemCount==1;
    }
}

4.总结
（1）与树的深度优先遍历不同，这里相当于图的深度优先遍历，因此是有可能遍历回原来的节点的（可以理解为二叉树中子节点遍历回其父节点了，但是这是不可能的），所以一定要记录下走过的路径，然后遇到走过的节点就跳过。
（2）我的方法中是：走到一个节点，再记录一个节点。而网友答案的方法是：先记录下要往下走的节点，从list中删去该节点，然后再往下遍历（因为已经记录下来了，所有不用从列表中找）。
（3）网友的答案和我的答案都可以避免在之后的路程中，还遍历之前走过的节点。但是网友的答案必须在从一个节点开始走不通的情况下，用history记录下该节点，这个history和我的答案中的history含义不同，我记录的是走过的节点，不一定从这个节点往下走就走不通，而网友的history是确定从这个节点往下走走不同才记录进去。而我的答案呢，不用记录走不通的节点，因为只要正在遍历for循环中的下一个节点了，就说明for循环的上一个节点往下走是走不通的。
（4）剪枝操作，网友的答案和我的答案正好巧了，都是同一句话，history中包含当前节点，就返回false，即剪枝。
（5）如果题目改成输出所有符合条件的路径，那么我的答案才是正确的，网友的答案只能输出一个路径，而我的答案只需要改动一下，将当前res记录到一个list中，然后res重置即可，就可以得到所有路径，而且这些输出的路径不重复。根本原因是我的history的作用只是告诉我们这个节点走过没有，并没有说这个节点往下走走不通，所以我的答案的意思就是这个节点走过了，可能能走通，可能走不通，若能走通我肯定已经把路径存起来了，若走不通的话我也不用知道，反正我也不会再从这个节点往下走了。