简介

树是数据结构和算法中的大头，掌握树的算法思想显得多么的重要，下面将从几个大的方面进行展开说明：递归、层次遍历、前中后序遍历、二叉查找树（BST）、字典树（Trie）

学习目标

学会把思路转化为代码，知道如何提取别人解法的核心思路。简单来说就是手撕代码。

框架

会了框架你就不会得0分啦，但除了框架你还要注意细节就好。
参照数据结构与算法学习指南

递归

1. 树的高度
2. 平衡树
3. 两节点的最长路径
4. 翻转树
5. 归并两棵树
6. 判断路径和是否等于一个数
7. 统计路径和等于一个数的路径数量
8. 子树
9. 树的对称
10. 最小路径
11. 统计左叶子节点的和
12. 相同节点值的最大路径长度
13. 间隔遍历
14. 找出二叉树中第二小的节点

    public int findSecondMinimumValue(TreeNode root) {
      if(root == null) return 0;
      if(root.left == null && root.right == null) return -1;
      int leftvalue = root.left.val;
      int rightvalue = root.right.val;
      if(leftvalue == root.val) leftvalue =  findSecondMinimumValue(root.left);
      if(rightvalue == root.val) rightvalue =  findSecondMinimumValue(root.right);
      if(leftvalue != -1 && rightvalue != -1) return Math.min(leftvalue,rightvalue);
      if(leftvalue != -1) return leftvalue;
      return rightvalue;

    }

递归总结（都是细节）

if条件、递归思想，必须有停止条件。有递也有归。提取私有变量作为公有变量（一个变两个函数）。
一、只有root，没有子树
二、一棵子树
三、两棵子树

层次遍历(BFS:Breadth first search)

1. 一棵树每层节点的平均数
2. 得到左下角的节点

总结：队列、数组、while条件
未掌握：集合的常用方法使用。
List< Double> arr = new ArrayList<>();
Queue< TreeNode> queue = new LinkedList<>();

前中后序遍历(DFS) (栈)

递归实现前中后序遍历
void dfs(TreeNode root){
visit(root);
dfs(root.left);
dfs(root.right);
}(前序遍历、其他类同)

1. 非递归实现二叉树的前序遍历
2. 非递归实现二叉树的后序遍历( Collections.reverse(ret);倒序输出
   )
3. 非递归实现二叉树的中序遍历
   总结：递归（在于visit()后面）与非递归(在于pop()后面)

二叉搜索树（Binary Search Tree、BST）:左边节点数 < root < 右边节点数（左小右大）

套路:

算法设计的总路线：明确一个节点要做的事情，剩下的交给框架。

二叉树的框架

void traverse(TreeNode root){
    //root需要做什么？在这做。
   //其他的不用root操心，交给框架
   traverse(root.left);
   traverse(root.right);
}

下面是两个简单的二叉树的例子。
0. 如何把二叉树所有的节点中的值都加1？

void plusOne(TreeNode root){
  if(root=NULL) return;
  root.val+=1;
  plusOne(root.left);
  plusOne(root.right);
}

1. 如何判断二叉树是否完全相同？

   boolean isSameTree(TreeNode root1,TreeNode root2){
     if(root1=NULL&&root2=NULL) return true;
     if((root1=NULL&&root2!=NULL)||(root1!=NULL&&root2=NULL)) return false;
     if(root1.val != root1.val) return true;
     isSameTree(root.left);
     isSameTree(root.right);
   }

   二叉查找数的遍历框架

   void BST(TreeNode root,target){
   if(root.val == target )
      //找到目标，做点什么
   if(root.val < target) BST(root.right,target);
   if(root.val > target) BST(root.left,target);
   }

2. 修剪二叉查找树

3. 寻找二叉查找树的第 k 个元素

4. 把二叉查找树每个节点的值都加上比它大的节点的值

5. 二叉查找树的最近公共祖先

6. 二叉树的最近公共祖先

7. 从有序数组中构造二叉查找树

8. 根据有序链表构造平衡的二叉查找树

9. 在二叉查找树中寻找两个节点，使它们的和为一个给定值(
   未掌握点：List arr = new ArrayList<>()的使用)

10. 在二叉查找树中查找两个节点之差的最小绝对值(中序左边比右边小)

11. 寻找二叉查找树中出现次数最多的值 (数组的使用、设置多个成员变量、多个判断if)

12. 判断BST的合法性(*)

    boolean isValidBST(TreeNode root){
        isValidBST(root,NULL,NULL);
    }
     boolean isValidBST(TreeNode root,TreeNode min,TreeNode max){
       if(root==NULL) return true;
       if((min.val>=root.val&&min!=NULL)||(max.val<=root.val&&max!=NULL)) return false;
       return  isValidBST(root.left)&&isValidBST(root.right); 
     }

13. 寻找一个数是否存在？

    1.boolean isInBST(TreeNode root,int target){
        if(root == NULL) return false;
        if(root.val==target) return true;
        return isInBST(root.left,target)||isInBST(root.right,target);    
        }//递归    
        2.boolean isInBST(TreeNode root,int target){
        if(root == NULL) return false;
        if(root.val==target) return true;
        if(root.val<target)    return isInBST(root.right,target);
        if(root.val>target)    return isInBST(root.left,target);
     }//把左小右大带上，二分查找。

14. 在BST中插入一个数
    遍历就是找，访问就是改(返回的是TreeNode类型)

    TreeNode insertNode(TreeNode root,int val){
          if(root == NULL) return new TreeNode(val);
      if(root.val<val)
          root.right = insertNode(root.right,val);
      if(root.left)
          root.left = insertNode(root.left,val);
      return root;
      }

15. 在BST中删除一个数

    TreeNode delectNode(TreeNode root,int val){
      if(root.val == val) {
        if(root.right==NULL&&root.left==NUll) {return NULL}
        if(root.right==NULL){return root.left;}
        if(root.left == NULL){return root.right;}
        if(root.left != NULL && root.right != NULL){
          TreeNode minNode = getMin(root.right);
          root.val = minNode.val;
          root.right = delectNode(root.right,minNode.val)}
      }
      if(root.val > val)  {
          root.left = delectNode(root.left.val)
         }
      if(root.val < val)  {
          root.right = delectNode(root.right.val)
         }
       return root;
        }
    
    TreeNode getMin(TreeNode node){
      while(node.left != NULL) node = node.left;
      return node;
    }

Trie

Trie树就是传说中的字典树，常用于处理字符，例如智能补全功能、敏感词过滤都和Trie数有关。（三个指针）

1. 实现一个 Trie（insert()、search()、startwith()）

   class Trie{
    private class Node{
      Node[] childs = new Node[26];
      boolean isLeaf;
    }
    public Trie(){}
    private Node root = new Node();
    public void insert(String word){
        insert(word,root);
        };
    public void insert(String word,Node root){
      if(root==NULL) return;
      if(word.length()==0){
        root.isLeaf = true;
        return ;
      }
      int index = indexForChar(word.chatAt(0));
      if(node.childs[index] == NULL){
            node.childs[index]=new Node();
      }
      insert(word.substring(1),node.childs[index]);
    }
   
    public boolean search(String word){
         return search(word,root);
      };
    public boolean search(String word,Node root){
      if(root==NULL) return;
      if(word.length()==0){
      return root.isLeaf;
     }
      int index = indexForChar(word.chatAt(0));
      return search(
            word.substring(1),node.childs[index]);
    }
   
    public boolean startwith(String word){
           return startwith(word,root);
       }; 
    public boolean startwith(String word,Node root){
      if(root==NULL) return;
      if(word.length()==0){
      return root.isLeaf;
     }
      int index = indexForChar(word.chatAt(0));
      return startwith(
          word.substring(1),node.childs[index]);
     }
   
     private int indexForChar(char c){
         return c - 'a';
      }
   }

2. 实现一个 Trie，用来求前缀和

3. 敏感词过滤是如何实现的？什么是字典树（trie）
   三个指针，一个指root，两个指向字符串
   敏感词过滤解法介绍

赏

谢谢你请我吃糖果

微信