树

树常用遍历方式：DFS与BFS

• DFS递归写法

public void dfs(TreeNode root){
    if(root == null)
        return;
    System.out.println(root.val);
    dfs(root.left);
    dfs(root.right);
}

• DFS非递归写法：利用栈的先进后出

申请一个栈，先将根节点压栈

栈不为空时

• 弹出栈顶元素

• 对栈顶元素做相应逻辑处理（条件判断或加工）

• 先判断右子树是否为空，不为空则右孩子压入栈

• 再判断左子树是否为空，不为空则左孩子压入栈

• 先压右，再压左，由于先进后出，便可使左子树先出栈，左子树的子树又进栈，实现左子树深度优先遍历

public ArrayList<Integer> dfs(TreeNode root){
    ArrayList<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp;
    
    if(root == null)
        return res;
    
    stack.push(root);
    while(!stack.isEmpty()){
        temp = stack.pop();
        res.add(temp.val);
        if(temp.right != null)
            stack.push(right);
        if(temp.left != null)
            stack.push(left);
    }
    return res;
}

• BFS：利用队列

申请一个队列，根节点进队

当队列不为空时

• 队首元素出队
• 对队首元素做相应逻辑处理（条件判断或加工）
• 先判断左子树是否为空，不为空则左孩子入队
• 再判断右子树是否为空，不为空则右孩子入队
• 先左后右，由于队列先进先出，每一层节点会从左到右出队，实现广度优先遍历

public ArrayList<Integer> bfs(){
    ArrayList<Integer> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    TreeNode temp;

    if(root == null)
        return res;
    
    queue.offer(root);
    while(!queue.isEmpty()){
        temp = queue.poll();
        res.add(temp.val);
        if(temp.left != null)
            queue.offer(temp.left);
        if(temp.right != null)
            queue.offer(temp.right);
    }
    return res;
}

树常用遍历方式：先序、中序、后序

• 递归

// 先序
public void preOrderByRecursion(TreeNode root){
    if(root == null)
        return;
    System.out.println(root.val);
    preOrderByRecursion(root.left);
    preOrderByRecursion(root.right);
}

// 中序
public void inOrderByRecursion(TreeNode root){
    if(root == null)
        return;
    preOrderByRecursion(root.left);
    System.out.println(root.val);
    preOrderByRecursion(root.right);
}

// 后序
public void postOrderByRecursion(TreeNode root){
    if(root == null)
        return;
    preOrderByRecursion(root.left);
    preOrderByRecursion(root.right);
    System.out.println(root.val);
}

• 利用栈

// 先序：根->左->右
public void preOrder(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp = root;
    while(temp!=null || !stack.isEmpty()){
        // 先访问当前节点，再遍历当前节点的所有左节点
        while(temp != null){
            // 先访问
            System.out.println(root.val);
            // 将当前节点和所有左节点压入栈
            stack.push(temp);
            temp = temp.left;
        }
        // 栈顶元素出栈，遍历其右节点
        if(!stack.isEmpty()){
            temp = stack.pop();
            temp = temp.right;
        }
    }
}

// 中序：左->根->右
public void inOrder(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp = root;
    while(temp!=null || !stack.isEmpty()){
        // 遍历当前节点和所有左节点
        while(temp != null){
            // 将当前节点和所有左节点压入栈
            stack.push(temp);
            temp = temp.left;
        }
        // 栈顶元素出栈，先访问，再遍历其右节点
        if(!stack.isEmpty()){
            temp = stack.pop();
            System.out.println(temp.val);
            temp = temp.right;
        }
    }
}

// 后序：左->右->根
// 用链表保存序列结果。若是先序遍历，则每个节点都插入链表尾部，若是后序遍历，则可插入头部
// 修改思路：
// 	1.修改先序遍历中，节点写入链表中的位置，由 插入队尾 改为 插入队首
// 	2.修改先序遍历中，每次 先查看左节点再查看右节点 的逻辑，变为 先查看右节点，再查看左节点
public List<Integer> postOrder(TreeNode root){
    LinkedList<Integer> res = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp = root;
    while(temp!=null || !stack.isEmpty()){
        if(temp != null){
            stack.push(temp);
            res.addFirst(temp.val);
            temp = temp.right;
        }else{
            temp = stack.pop();
            temp = temp.left;
        }
    }
    return res;
}

层次遍历

从上往下打印二叉树（层次遍历）（简单）

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    // 利用队列，root进队，while队列不为空，队首出队，输出，将左右孩子入队
    ArrayList<Integer> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    TreeNode temp;

    if(root == null)
        return res;
    queue.offer(root);
    while(!queue.isEmpty()){
        temp = queue.poll();
        res.add(temp.val);
        if(temp.left != null)
            queue.offer(temp.left);
        if(temp.right != null)
            queue.offer(temp.right);
    }
    return res;
}

多行打印（层次遍历按行输出）（中等）

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    // 层序遍历，使用队列，打印每行结果
    // while遍历每一行，for遍历当前行每个节点

    // 初始准备
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    TreeNode temp;
    // 特殊情况
    if(pRoot == null){
        return res;
    }
    queue.offer(pRoot);
    while(!queue.isEmpty()){
        int size = queue.size();
        ArrayList<Integer> row = new ArrayList<Integer>();
        for(int i = 0; i < size; i++){
            temp = queue.poll();
            row.add(temp.val);
            if(temp.left != null){
                queue.offer(temp.left);
            }
            if(temp.right != null){
                queue.offer(temp.right);
            }
        }
        res.add(row);
    }
    return res;
}

之形打印（反转层次遍历）（中等）

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    // 层序遍历 + 判断奇偶行反转
    /* 层序遍历：利用队列。
           根节点入队，循环判断队列是否为空
           队列不为空，队首出队，输出；若队首节点有孩子节点，则左右入队
           队列为空，即当前行已经全部出队，进入下一次循环
           输出结果即为层序遍历结果*/
    // 此题中，设置ArrayList保存当前行，奇数行不反转，偶数行反转
    // 得到当前行需要在每次循环时，取队列长度，循环进行出队和孩子节点入队
    // 外层while次数为树的行数，内层for次数为当前行节点个数

    // 初始化：队列、结果数组、奇偶行标记、出队时临时节点声明
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    boolean isReverse = false;
    TreeNode temp;
    // 特殊情况：pRoot为空，直接返回空list
    if(pRoot == null){
        return res;
    }
    queue.offer(pRoot);
    // 循环
    while(!queue.isEmpty()){
        int size = queue.size();
        ArrayList<Integer> row = new ArrayList<Integer>();
        for(int i = 0; i < size; i++){
            temp = queue.poll();
            row.add(temp.val);
            if(temp.left != null){
                queue.offer(temp.left);
            }
            if(temp.right != null){
                queue.offer(temp.right);
            }
        }
        if(isReverse){
            Collections.reverse(row);
        }
        isReverse = !isReverse;
        res.add(row);
    }
    return res;
}

二叉搜索树

判断是否是二叉搜索树的后序遍历（中等）

public boolean VerifySquenceOfBST(int[] sequence){
    // 递归：
    // 终止条件：开始位置 >= 结束位置
    // 递归前逻辑处理：
    // 1.数组最后一个元素为根节点
    // 2.从左到右遍历数组，判断节点值是否小于根节点值
    //   若小于，则说明是左子树值
    //   若大于，则说明是右子树值，记录当前位置i
    // 3.遍历当前位置到数组结尾-1位置，判断节点值是否大于根节点值
    //   若不大于，则说明不是二叉搜索树，返回false
    // 递归：对左子树和右子树部分都进行递归

    // 代码：
    // 特殊情况：题目说明空树不是二叉搜索树
    if(sequence.length == 0){
        return false;
    }
    return dfs(sequence, 0, sequence.length);
}

private boolean dfs(int[] sequence, int start, int end){
    // 终止条件：
    if(start >= end-1){
        return true;
    }
    // 数组最后一位是根节点
    int root = sequence[end-1];
    // 找到左子树结束位置i
    int i = start;
    while(i < end-1 && sequence[i] < root){
        i++;
    }
    // 遍历右子树节点，判断是否符合二叉搜索树规则，若不符合则直接返回false
    for(int j = i; j < end; j++){
        if(sequence[j] < root){
            return false;
        }
    }
    // 对左右子树都进行递归调用判断
    return dfs(sequence,start,i) && dfs(sequence,i,end-1);
}

寻找二叉搜索树的第k个节点（中等）

• 递归

int count = 0;
int res = -1;
public int KthNode (TreeNode proot, int k) {
    // write code here
    // 本题实际是直接中序遍历，输出第k个值
    // 方法1：递归
    if(proot == null || k < 0)
        return -1;
    KthNode(proot.left,k);
    count++;
    if(count == k)
        return res = proot.val;
    KthNode(proot.right,k);
    return res;

    // 方法2：利用栈
    // 设置temp指针深度优先遍历二叉树
    // 若temp为空说明这个方向已遍历结束，则换个方向继续遍历
    // 若temp为空，栈不为空，则弹出栈顶元素作为新的temp节点
    // 若temp为空，栈也为空，则说明整个二叉树已遍历完成
}

• 利用栈

public int KthNode (TreeNode proot, int k) {
    // write code here
    // 本题实际是直接中序遍历，输出第k个值

    // 方法2：利用栈
    // 设置temp指针深度优先遍历二叉树
    // 若temp为空说明这个方向已遍历结束，则换个方向继续遍历
    // 若temp为空，栈不为空，则弹出栈顶元素作为新的temp节点
    // 若temp为空，栈也为空，则说明整个二叉树已遍历完成
}

和相同路径

寻找和相同的路径1（简单）

• 题目：判断是否有此路径（到叶子结点路径）

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1. 该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2. 叶子节点是指没有子节点的节点
3. 路径只能从父节点到子节点，不能从子节点到父节点
4. 总节点数目为n

• 递归

public boolean hasPathSum (TreeNode root, int sum) {
    // write code here
    // 方法1：递归
    // 从根节点往下走，每经过一个节点就减掉当前节点的val，一直到叶子结点
    // 若减完叶子结点后，sum == 0，则说明存在这样的路径，返回true
    // 若遍历完所有节点也未返回true，则说明没有这样的路径，返回false

    // 终止条件：root == null，根节点（即当前节点）为空
    // 递归前逻辑处理：判断是否为叶子结点，且sum == 0，若都满足则返回true
    if(root == null){
        return false;
    }
    if(root.left == null && root.right == null && root.val == sum){
        return true;
    }
    return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
}

• 利用栈

public boolean hasPathSum (TreeNode root, int sum) {
    // 方法2：利用栈
    // 从根节点往下走，把每个经过的节点都压入栈
    // 当栈不为空时，栈顶元素出栈
    //     判断是否左右节点都为空且值与sum相等，若都满足则说明存在此路径，返回true
    //     若不满足，则将左右孩子压入栈
    // 若遍历完后都未找到路径，则返回false
    if (root == null)
        return false;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp;
    stack.push(root);
    while(!stack.isEmpty()){
        temp = stack.pop();
        if(temp.left == null && temp.right == null){
            if(temp.val == sum){
                return true;
            }
        }
        if(temp.right != null){
            temp.right.val = temp.val + temp.right.val;
            stack.push(temp.right);
        }
        if(temp.left != null){
            temp.left.val = temp.val + temp.left.val;
            stack.push(temp.left);
        }
    }
    return false;
}

寻找和相同的路径2（中等）

• 题目：找出所有路径（到叶子结点路径）

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。

1. 该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2. 叶子节点是指没有子节点的节点
3. 路径只能从父节点到子节点，不能从子节点到父节点
4. 总节点数目为n

• 递归

ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
Stack<Integer> path = new Stack<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
    // 方法1：递归，利用栈保存路径
    // 终止条件：root为空，也是特殊情况判断，返回结果路径组
    // 递归前逻辑处理：
    //     将当前节点压入栈，expectNumber减去当前节点值
    //     判断是否为叶子节点，且expectNumber为0，满足则将此路径加入结果路径组中
    // 递归：左子树递归，右子树递归，不需要返回值
    // 递归后逻辑处理：将最后入栈的节点删除（若是正确路径，则已加入结果组；若是错误路径，则回到错误之前）

    if(root == null)
        return res;

    path.push(root.val);
    expectNumber -= root.val;
    if(expectNumber == 0 && root.left == null && root.right == null){
        res.add(new ArrayList<Integer>(path));
    }

    FindPath(root.left,expectNumber);
    FindPath(root.right,expectNumber);
    path.pop();

    return res;
}

寻找和相同的路径3（中等）

• 题目

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

1. 该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2. 总节点数目为n

• 两次dfs

public int FindPath (TreeNode root, int sum) {
    // write code here
    // 方法1：两次dfs
    // 对根节点（当前节点）进行dfs递归遍历，寻找是否有满足条件的路径
    // 对左右孩子执行FindPath递归，即对二叉树每个节点都进行遍历判断
    // 时间复杂度：O(n2) --> n为二叉树节点，两次dfs嵌套递归
    // 空间复杂度：O(n) --> 每次dfs最深递归栈都为n

    if(root == null){
        return res;
    }
    dfs(root,sum);
    FindPath(root.left,sum);
    FindPath(root.right,sum);
    return res;
}

int res = 0;
private void dfs(TreeNode root, int sum){
    if(root == null){
        return;
    }
    if(sum == root.val){
        res++;
    }
    dfs(root.left,sum-root.val);
    dfs(root.right,sum-root.val);
}

树的结构

求原二叉树的镜像

• 递归

public TreeNode Mirror (TreeNode pRoot) {
    // write code here
    // 方法1：递归，调换左右子树
    // 终止条件：根节点为空，返回null
    if(pRoot == null){
        return null;
    }
    // 对左子树求镜像
    Mirror(pRoot.left);
    // 调换左右子树
    TreeNode temp = pRoot.left;
    pRoot.left = pRoot.right;
    pRoot.right = temp;
    // 对右子树求镜像（也就是调换后的左子树）
    Mirror(pRoot.left);
    return pRoot;
}

• BFS广度优先

public TreeNode Mirror (TreeNode pRoot) {
    // write code here
    // 方法2：BFS广度优先，利用队列
    // BFS原是层次遍历，根节点入队，若队列不为空，队首出队输出，左右孩子进队
    // 本题在队首出队后，交换左右孩子，即可得到镜像二叉树
    // 特殊情况
    if(pRoot == null)
        return null;
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode temp1,temp2;
    queue.offer(pRoot);
    while(!queue.isEmpty()){
        temp1 = queue.poll();
        //交换
        temp2 = temp1.left;
        temp1.left = temp1.right;
        temp1.right = temp2;
        //左右孩子入队
        if(temp1.left!=null)
            queue.offer(temp1.left);
        if(temp1.right!=null)
            queue.offer(temp1.right);
    }
    return pRoot;
}

• DFS深度优先

public TreeNode Mirror (TreeNode pRoot) {
    // write code here
    // 方法3：DFS深度优先，利用栈
    if(pRoot == null)
        return null;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp1,temp2;
    stack.push(pRoot);
    while(!stack.isEmpty()){
        temp1 = stack.pop();// 出栈
        // 交换
        temp2 = temp1.left;
        temp1.left = temp1.right;
        temp1.right = temp2;
        // 先压右子树再压左子树，出栈即为先左后右
        if(temp1.right != null)
            stack.push(temp1.right);
        if(temp1.left != null)
            stack.push(temp1.left);
    }
    return pRoot;
}

• 中序遍历：非递归，利用栈

public TreeNode Mirror (TreeNode pRoot) {
    // write code here
    // 方法4：中序遍历，非递归，利用栈
    if(pRoot == null)
        return null;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode temp1 = pRoot,temp2;
    while(temp1 != null || !stack.isEmpty()){
        // 遍历左子树，找到最深的节点，经过节点压入栈
        while(temp1 != null){
            stack.push(temp1);
            temp1 = temp1.left;
        }
        // 出栈，往回走向根节点，然后再遍历右子树
        if(!stack.isEmpty()){
            temp1 = stack.pop();
            temp2 = temp1.left;
            temp1.left = temp1.right;
            temp1.right = temp2;
            //遍历右子树(此处左右交换)
            temp1 = temp1.left;
        }
    }
    return pRoot;
}

对称：判断给定二叉树是否是自身的镜像

• 递归

public boolean isSymmetrical(TreeNode pRoot) {
    // 递归，判断每个子树是否对称
    // 传入左右两个节点
    //    若都为空，则对称
    //    若一个为空，则不对称
    //    若值不相等，则不对称
    //    其他情况，则继续递归判断其子树是否对称
    return checkSymmetrical(pRoot,pRoot);
}

private boolean checkSymmetrical(TreeNode left,TreeNode right){
    if(left == null && right == null)
        return true;
    if(left == null || right == null)
        return false;
    if(left.val != right.val)
        return false;
    return checkSymmetrical(left.left,right.right) 
        && checkSymmetrical(left.right,right.left);
}

• 层次遍历

public boolean isSymmetrical(TreeNode pRoot) {
    // 层次遍历，用数组保存每一层（包括空节点），判断此数组是否对称
    if(pRoot == null){
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    TreeNode temp;
    TreeNode emptyNode = new TreeNode(1001);//占位节点
    queue.offer(pRoot);
    while(!queue.isEmpty()){
        int n = queue.size();
        ArrayList<Integer> row = new ArrayList<>();
        for(int i = 0; i<n; i++){
            temp = queue.poll();
            row.add(temp.val);
            //不让空节点的左右孩子入队
            if(!temp.equals(emptyNode)){
                queue.offer(temp.left!=null?temp.left:emptyNode);
                queue.offer(temp.right!=null?temp.right:emptyNode);
            }
        }
        //判断当前层次是否对称
        if(!checkSymmetrical(row))
            return false;
    }
    return true;
}
private boolean checkSymmetrical(ArrayList<Integer> list){
    int start = 0;
    int end = list.size()-1;
    while(start < end){
        //不能用!=，必须用equals，只判断内容是否相同
        if(!list.get(start).equals(list.get(end)))
            return false;
        start++;
        end--;
    }
    return true;
}

求树的深度

• 递归

public int TreeDepth(TreeNode root) {
    // 递归
    if(root == null)
        return 0;
    return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}

• 层次遍历

public int TreeDepth(TreeNode root) {
    // 层次遍历（队列实现）
    // 将每一层的节点全部入完队后，计数++
    int height = 0;
    if(root == null)
        return height;
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode temp;
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i = 0; i<size; i++){
            temp = queue.poll();
            if(temp.left != null)
                queue.offer(temp.left);
            if(temp.right != null)
                queue.offer(temp.right);
        }
        // 一层节点全部入队
        height++;
    }
    return height;
}

平衡：判断二叉树左右深度差是否小于1

• 双层DFS

public boolean IsBalanced_Solution(TreeNode root) {
    // 双层dfs，递归嵌套
    // 第一层用于递归求二叉树深度，第二层用于对每个节点判断左右子树高度差是否大于等于2
    if (root == null)
        return true;
    return IsBalanced_Solution(root.left) 
        && IsBalanced_Solution(root.right) 
        && Math.abs(getDeep(root.left) - getDeep(root.right))<2;

}
private int getDeep(TreeNode root){
    if(root == null)
        return 0;
    return Math.max(getDeep(root.left),getDeep(root.right))+1;
}

• 回溯

public boolean IsBalanced_Solution(TreeNode root) {
    // 回溯：每个节点向父节点报告自己的深度，若子节点的深度差大于1，则不是平衡树
    if(reportDeep(root)==-1)
        return false;
    return true;
}

private int reportDeep(TreeNode root){
    // 若此节点为空，则返回深度0
    if(root == null)
        return 0;
    // 递归找到左子树的深度
    int left = reportDeep(root.left);
    if(left == -1)
        return -1;
    // 递归找到右子树的深度
    int right = reportDeep(root.right);
    if(right == -1)
        return -1;
    // 判断左右子树深度差是否大于1
    if(Math.abs(left-right)>1)
        return -1;
    // 向父节点报告深度
    return Math.max(left,right)+1;
}

子结构

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root1 == null || root2 == null)//若有一个为空，则根据题意，子结构不同
        return false;
    // 判断当前子树是否与root2相同
    // （若上一个不满足）判断当前子树的左子树是否与root2相同
    // （若上一个不满足）判断当前子树的右子树是否与root2相同
    // （若都不满足）说明没有相同的子结构
    return isSame(root1, root2) 
        || HasSubtree(root1.left, root2) 
        || HasSubtree(root1.right,root2);
}

// 判断两子树是否相同
private boolean isSame(TreeNode root1,TreeNode root2){
    if(root2 == null)// 终止条件：子树2为空，即遍历完也未有不同
        return true;
    if(root1 == null)// 终止条件：子树2还未遍历完，子树1已空，则肯定不相同
        return false;
    return root1.val == root2.val // 判断值是否相等
        && isSame(root1.left,root2.left) // 同时判断左子树
        && isSame(root1.right,root2.right); // 同时判断右子树
}

找最近公共祖先

二叉树最近公共祖先

• 递归

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
    // write code here
    // DFS递归：
    // 特殊情况：root==null
    // 终止条件：o1o2中任意一个等于root值。说明在到达o1o2前没有最近公共祖先，此时root即为最近祖先
    // 递归逻辑处理：
    //    假设通过递归拿到最近公共祖先，分别对左右子树递归
    //    若对左子树递归，未得到祖先，则说明祖先在右子树上，返回右子树
    //    若对右子树递归，未得到祖先，则说明祖先在左子树上，返回左子树
    //    若都无结果，则返回root，当前节点即为最近祖先
    return commonAncestor(root,o1,o2).val;
}
private TreeNode commonAncestor(TreeNode root, int o1, int o2){
    if(root == null || root.val == o1 || root.val == o2)
        return root;
    TreeNode left = commonAncestor(root.left,o1,o2);
    TreeNode right = commonAncestor(root.right,o1,o2);
    if(left == null)
        return right;
    if(right == null)
        return left;
    return root;
}

• BFS广度优先

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
    // write code here
    // 非递归：
    // 利用队列BFS层次遍历，Map记录每个节点的父节点
    // 用Set保存目标节点o1到根节点的路径，再遍历o2到根节点的路径，判断是否有相同值
    // 至少有根节点这一个相同值
    Map<Integer,Integer> parent = new HashMap<>();
    Queue<TreeNode> queue = new LinkedList<>();
    parent.put(root.val,Integer.MIN_VALUE);
    TreeNode temp;
    queue.offer(root);
    // 不需要遍历完整棵树，只需要到o1，o2节点即可
    while(!parent.containsKey(o1) || !parent.containsKey(o2) ){
        temp = queue.poll();
        if(temp.left != null){
            queue.offer(temp.left);
            parent.put(temp.left.val,temp.val);
        }
        if(temp.right != null){
            queue.offer(temp.right);
            parent.put(temp.right.val,temp.val);
        }
    }
    Set<Integer> path = new HashSet<>();
    while(parent.containsKey(o1)){
        path.add(o1);
        o1 = parent.get(o1);
    }
    while(!path.contains(o2)){
        o2 = parent.get(o2);
    }
    return o2;
}

二叉搜索树最近公共祖先

public int lowestCommonAncestor (TreeNode root, int p, int q) {
    // write code here
    // 递归
    // 特殊情况：root == null
    // 终止条件：root是否到达p或q节点
    //    若到达，则说明在此之前都没有最近公共祖先，此root即为最近祖先
    // 递归逻辑判断：
    //    假设递归已得到祖先节点，即已知左右子树中是否有祖先
    //    有三种情况：
    //    1.pq都小于root值，则说明root不是最近祖先，应对左子树递归找到祖先
    //    2.pq都大于root值，则说明root不是最近祖先，应对右子树递归找到祖先
    //    3.其他情况，pq分散在root的左右子树，此时root即为最近祖先，返回root
    return commonAncestor(root,p,q).val;
}
private TreeNode commonAncestor(TreeNode root, int p, int q){
    if(root==null)
        return null;
    if(root.val == p || root.val == q)
        return root;
    if(p < root.val && q < root.val)
        return commonAncestor(root.left,p,q);
    else if(p > root.val && q > root.val)
        return commonAncestor(root.right,p,q);
    else 
        return root;
}

序列化

重建二叉树

public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
    // 1 2 4 7 3 5 6 8
    // 4 7 2 1 5 3 8 6 
    // pre[0]为根节点

    // 递归
    // 思路：
    //    由先序序列的第一个节点，确定根节点，构建根节点
    //    循环遍历中序序列，找到根节点位置i
    //    将中序序列切分成左右子树（vin[i]前后）
    //    将先序序列切分成左右子树（pre[1,i)，pre[i+1,pre.length)）
    //    对左右子树分别递归执行以上操作

    // 终止条件：pre或vin为空，代表此方向已构造结束
    if(pre.length == 0 || vin.length == 0)
        return null;

    TreeNode root = new TreeNode(pre[0]);
    for(int i = 0; i<vin.length; i++){
        if(pre[0] == vin[i]){
            root.left = 
                reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),
                                      Arrays.copyOfRange(vin,0,i));
            root.right = 
                reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),
                                      Arrays.copyOfRange(vin,i+1,vin.length));
            break;
        }
    }
    return root;
}

序列化与反序列化

TreeNode emptyNode = new TreeNode(-1);
public String Serialize(TreeNode root) {
    // 层次遍历序列化，利用队列，结果加入StringBuilder
    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode temp;

    if(root == null)
        return "";

    queue.offer(root);
    while(!queue.isEmpty()){
        temp = queue.poll();
        sb.append(temp.val + ":");
        if(!emptyNode.equals(temp)){
            queue.offer(temp.left == null? emptyNode:temp.left);
            queue.offer(temp.right == null? emptyNode:temp.right);
        }
    }
    return sb.toString();
}
private TreeNode Deserialize(String str) {
    // 对字符串分割，找到根节点值，构建根节点
    // 利用队列进行层次遍历
    // for循环遍历字符串组，每次取左右两个节点，若值不为-1，则构建真实节点

    // 特殊情况：str为空，返回空树
    if(str.equals(""))
        return null;

    String[] vals = str.split(":");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    TreeNode temp;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    for(int i = 1; i < vals.length; i+=2){
        temp = queue.poll();
        int leftV = Integer.parseInt(vals[i]);
        int rightV = Integer.parseInt(vals[i+1]);
        if(leftV != -1){
            temp.left = new TreeNode(leftV);
            queue.offer(temp.left);
        }
        if(rightV != -1){
            temp.right = new TreeNode(rightV);
            queue.offer(temp.right);
        }
    }
    return root;
}