树类算法总结整理（递归与回溯）

总结概览

1. 深度优先遍历 & 回溯

遍历和回溯都是对问题的全局可能性进行搜索的算法，适合求所有可能结果或最好结果的题目。深度优先遍历每次选择一个节点后，以该节点为根继续进行下一步选择，为避免重复，需要维护一个已访问节点的列表
回溯就是在深度优先遍历的基础上，加入了处理与反处理的步骤。

List<List<>> lists; // 记录所有结果
List<> list; // 记录单个结果
boolean[] visited; // 记录已经走过的路径
//            当有条件判断时，有可能条件能够保证不走重复的路，此时就不需要visited
//             比如，在for循环的if条件中，只有可选节点比当前节点值小才会走，这时走了可选节点后一定不会回走当前节点。
// 当进入该函数时，保证所做的选择已经影响了visited和当前结果list
public void dfs(可以走的路径){  
    // 截止条件
    if ( 不满足条件且后面已不再可能有满足条件的结果 ) return;
    if ( 满足记录结果的条件 ){
        // 收集结果
        xxx
        return;
    }
    for( 遍历可以走的路径 ){
        // 判断+处理
        if( 可以走 ) {
            // 处理
            xxx
            // 递归
            dfs(更新过的可以走的路径)
            // 反处理回到这次迭代前的状态
            xxx
        }
    }
}

1. 广度优先遍历（层序遍历）

   public void bfs(TreeNode root) {
    if (root == null) {
        return;
    }
    // 维护一个队列，按“出入”的循环，入的是出节点的子节点
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 在某些场景中，需要按层来遍历，如果不需要可直接去掉内循环的条件
        int size = queue.size();
        while (size > 0) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            size--;
        }
    }
   }

2. 中序遍历

   // 用中序遍历找二叉搜索树中第k小的值
   public int kthSmallest(TreeNode root, int k) {
    // 中序遍历
    // 迭代
    Deque<TreeNode> stack = new LinkedList<TreeNode>();
    while(!stack.isEmpty() || root!=null){
        // 加入左节点
        while(root!=null){
            stack.push(root);
            root=root.left;
        }
        root = stack.pop();
        // 处理
        k--;
        if(k==0){
            break;
        }
        // 切换到右节点
        root = root.right;
    }
    return root.val;
   }

3. 前序遍历

   // 前序，迭代
   List<TreeNode> result = new ArrayList<TreeNode>();
   public List<Integer> preorderTraversal(TreeNode root) {
    if(root == null) 
        return result;
    // 维护一个显式的栈
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    while(!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        // 先压右节点
        if(node.right != null) stack.push(node.right);
        // 再压左节点
        if(node.left != null) stack.push(node.left);
    }
    return result;
   }

4. 后序遍历

后序迭代的思路和其他不太一样，在收集结果时是从后往前收集，后序要求“左-右-根”，则栈按照“根-右-左”的顺序出栈，出栈节点插入结果队列的开头。与之对应，压栈的顺序为压根，弹根，压左，压右，弹右，弹左。

public List<Integer> postorderTraversal(TreeNode root) {
    if(root == null) return result;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);   //首先将根节点压栈
    while(!stack.isEmpty()) {
        TreeNode ele = stack.pop(); //首先出栈的为根节点，其后先出右子节点，后出左子节点
        if(ele.left != null)
            stack.push(ele.left);  // 先将左子节点压栈
        if(ele.right != null) {
            stack.push(ele.right); // 后将右子节点压栈
        }
        result.add(0, ele.val); // 因为出栈顺序为“根右左”，所以需要每次将元素插入list开头
    }
    return result;
}

1. 前缀树（字典树）

104. 二叉树的最大深度

思路：深度优先遍历 or 广度优先遍历。

// 深度优先遍历
public int maxDepth(TreeNode root) {
    // 截止条件
    if (root == null) return 0;
    // 对某节点的子节点进行横向遍历，递归
    // 由于是二叉树，只有两次递归
    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);
    return Math.max(leftHeight, rightHeight) + 1;  
}

100. 相同的树

判断两个树是否相同。
思路：深度优先遍历 or 广度优先遍历。其中，广度优先遍历，在遍历到每个节点时，不仅要确认值是否相等，还要确认左右子树的结构是否相同。

124. 二叉树中的最大路径和

最大路径可以不经过根节点；不能走回头路（满足一笔画）

class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;
        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);
        // 返回节点的最大贡献值  ！！！注意，返回值与更新的最大路径和不同
        return node.val + Math.max(leftGain, rightGain);
    }
}

572. 另一棵树的子树

给定两个二叉树s和t，判断s中是否存在一个子树，与t完全相同。
思路一：先用一个深度优先搜索，用来检验两个子树是否完全相同；再用一个深度优先搜索来遍历s的各个节点，对每个节点调用第一个深度优先搜索来判断是否和t相同。因此，本题涉及两个深度优先搜索的嵌套。

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 深度优先搜索的嵌套
        return dfs(root, subRoot);
    }
    // 深度优先搜索遍历root的各个节点，与subRoot比较
    public boolean dfs(TreeNode root, TreeNode subRoot){
        // 截止条件
        if(root==null) return false;
        // 处理（判断）+ 递归遍历左右子树
        return dfsJudge(root, subRoot) || dfs(root.left, subRoot) || dfs(root.right, subRoot);
    }
    // 深度优先搜索判断两个树是否相同
    public boolean dfsJudge(TreeNode s, TreeNode t){
        // 截止条件
        if(s==null && t==null) return true;
        if(s==null || t==null || s.val!=t.val) return false;
        return dfsJudge(s.left,t.left) && dfsJudge(s.right,t.right);
    }
}

思路二：树哈希
树哈希，对树节点进行hash运算，相同结构的树拥有相同的hash值

class Solution {
    static final int lb = 2333, rb = 97755331, mb = 23333;
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 树哈希，对树节点进行hash运算，相同结构的树拥有相同的hash值
        if(root==null) return false;
        // 递归，用hashValue改写整个大树各个节点的值
        trans(root);
        int subRootValue = trans(subRoot);
        // 递归判断是否有相同的hashValue
        return dfs(root, subRootValue);
    }
    // 深度优先搜索遍历大树的子节点，是否与subRoot有相同的hash值
    public boolean dfs(TreeNode root, int subRootValue){
        // 截止条件
        if(root==null) return false;
        return root.val==subRootValue || dfs(root.left, subRootValue) || dfs(root.right, subRootValue);
    }
    // 递归计算树节点的hash值，并用hash值改写节点值
    // 哈希公式是：h(X) = Xv + mb + lb * h(Xl) + rb * h(Xr), 且h(null) = 1
    // lb = 2333, rb = 97755331, mb = 23333
    public int trans(TreeNode root){
        // 截止条件
        if(root==null) return 1;
        int hashValue = root.val+ + mb + trans(root.left)*lb + trans(root.right)*rb;
        root.val = hashValue;
        return hashValue;
    }
}

211. 添加与搜索单词 - 数据结构设计

思路：前缀树

class WordDictionary {
    private Trie root;
    public WordDictionary() {
        root=new Trie();
    }
    public void addWord(String word) {
        Trie node = this.root;
        for(int i=0;i<word.length();i++){
            char each = word.charAt(i);
            if(node.children[each-'a']==null){
                node.children[each-'a']=new Trie();
            }
            node = node.children[each-'a'];
        }
        node.isEnd=true;
    }
    public boolean search(String word) {
        return searchDFS(word,root);
    }
    public boolean searchDFS(String word, Trie node) {
        // 递归搜索
        if(word.length()==0) return node.isEnd;
        char each = word.charAt(0);
        if(each=='.'){
            // 搜索所有非空的children[j]，用递归
            for(int j=0;j<26;j++){
                if(node.children[j]!=null){
                    if(searchDFS(word.substring(1,word.length()),node.children[j])){
                        return true;
                    }
                }
            }
            return false;
        }else{
            // each为字母
            if(node.children[each-'a']==null){
                return false;
            }
            return searchDFS(word.substring(1,word.length()),node.children[each-'a']);
        }
    }
}
class Trie{
    Trie[] children;
    boolean isEnd;
    public Trie(){
        children=new Trie[26];
        isEnd=false;
    }
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */