[算法]死磕二叉树专题算法

1. 二叉树前序中序后序遍历（递归和非递归）

构造二叉树：

class Node{
    public String value;
    public Node left;
    public Node right;
    public Node(String value) {
        this.value = value;
    }
}

递归版前序遍历：

public static void preOrder(Node head){
        if(head != null){
            System.out.print(head.value + " ");
            preOrder(head.left);
            preOrder(head.right);
        }
    }

递归版中序遍历：

public static void inOrder(Node head){
        if(head != null){
            inOrder(head.left);
            System.out.print(head.value + " ");
            inOrder(head.right);
        }
    }

递归版后序遍历：

    public static void posOrder(Node head){
        if(head != null){
            posOrder(head.left);
            posOrder(head.right);
            System.out.print(head.value + " ");
        }
    }

非递归版前序遍历：

public static void preOrder(Node head){
        if(head != null){
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            while(!stack.isEmpty()){
                Node pop = stack.pop();
                System.out.print(pop.value + " ");
                if(pop.right != null)
                    stack.push(pop.right);
                if(pop.left != null)
                    stack.push(pop.left);
            }
        }
    }

非递归版中序遍历：

    public static void inOrder(Node head){
        if(head != null){
            Stack<Node> stack = new Stack<>();
            while(!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }else{
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
    }

非递归版后序遍历：

    public static void postOrder(Node head){
        if(head != null){
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack1.push(head);
            while(!stack1.isEmpty()){
                Node pop = stack1.pop();
                stack2.push(pop);
                if(pop.left != null){
                    stack1.push(pop.left);
                }
                if(pop.right != null){
                    stack1.push(pop.right);
                }
            }
            while(!stack2.isEmpty()){
                System.out.print(stack2.pop().value + " ");
            }
        }
    }

这里用了两个栈，其实一个栈也能实现，这里这样做是因为可以和前序遍历对比着记，比较容易。

2. 二叉树层次遍历

给定一个二叉树，返回其按层次遍历的节点值。（即从左到右访问）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果为：

[
  [3],
  [9,20],
  [15,7]
]

思路：类似于二叉树的非递归前序遍历，只不过采用队列，而非栈。

LeetCode：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class LevelOrder{
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //获取当前层的节点数
            int levelNum = queue.size();
            List<Integer> subList = new ArrayList<>();
            for (int i = 0; i < levelNum; i++) {
                TreeNode node = queue.poll();
                subList.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            list.add(subList);
        }
        return list;
    }
}

3. 二叉树的最大深度（深度）和最小深度

最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶节点的最长路径上的节点数。

案例：
给出二叉树 [3,9,20,null,null,15,7]，

返回最大深度为 3 。

LeetCode：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/

思路一：采用递归，每个节点的最大深度都等于左右子树深度大的那个加1。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class TreeMaxDepth {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

思路二：

层次遍历。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class TreeMaxDepthNotRecur {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int level = 0;
        while(!queue.isEmpty()){
            level++;
            int levelNum = queue.size();//每一层的节点个数
            for (int i = 0; i < levelNum; i++) {
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        return level;
    }
}

最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶节点的最短路径的节点数量。

LeetCode：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/

思路一：

参考最大深度递归思想，如果节点为null，直接返回0。如果左右子树均为null，返回1。如果只有左子树为null，返回右子树的最小深度加1。如果只有右子树为null，返回左子树的最小深度加1。如果左右子树均不为null，返回两者中较小的最小深度加1。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class TreeMinDepth{
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        if(root.left == null && root.right != null){
            return minDepth(root.right) + 1;
        }
        if(root.left != null && root.right == null){
            return minDepth(root.left) + 1;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return Math.min(left, right) + 1;
    }
}

思路二：

非递归，采用深度遍历的思想，当第一次出现左右子树均为null的节点，该节点所在层即为最小深度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class TreeMinDepthNotRecur {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int level = 0;
        while(!queue.isEmpty()){
            level++;
            int levelNum = queue.size();//每一层的节点个数
            for (int i = 0; i < levelNum; i++) {
                TreeNode node = queue.poll();
                if(node.left == null && node.right == null){
                    return level;
                }
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        return 0;
    }
}

4. 二叉树是否为平衡树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树的定义为：一棵二叉树中每个节点的两个子树的深度相差不会超过 1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]:

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]:

返回 false 。

LeetCode：https://leetcode-cn.com/problems/balanced-binary-tree/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class TreeIsBalanced {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        
        int diff = Math.abs(left - right);
        if(diff > 1){
            return false;
        }
        
        return isBalanced(root.left) && isBalanced(root.right);
    }
    
    public int treeDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        
        int left = treeDepth(root.left);
        int right = treeDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}

5. 查找两个节点的最近公共祖先

给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义： “对于有根树T的两个结点u、v，最近公共祖先表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。”（一个节点也可以是它自己的祖先）

        _______3______
       /              
    ___5__          ___1__
   /              /      
   6      _2       0       8
         /  
         7   4

例如，节点5和节点1的最近公共祖先是节点3；节点5和节点4的最近公共祖先是节点5，因为根据定义，一个节点可以是它自己的祖先。

LeetCode：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

public class LowestAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        if(left != null && right != null){
            return root;
        }
        return left != null ? left : right;
    }
}

6. 翻转二叉树

翻转一棵二叉树。

     4
   /   
  2     7
 /    / 
1   3 6   9

转换为：

     4
   /   
  7     2
 /    / 
9   6 3   1

思路：

两种方法，递归和非递归。

LeetCode：https://leetcode-cn.com/problems/invert-binary-tree/description/

递归：

public TreeNode mirror(TreeNode root){
        if(root == null){
            return null;
        }
        
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        
        mirror(root.left);
        mirror(root.right);
        return root;
    }

非递归：

public TreeNode mirrorNotRecur(TreeNode root){
        if(root == null){
            return null;
        }
        
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode poll = queue.poll();
            TreeNode node = poll.left;
            poll.left = poll.right;
            poll.right = node;
            
            if(poll.left != null){
                queue.offer(poll.left);
            }
            
            if(poll.right != null){
                queue.offer(poll.right);
            }
        }
        return root;
    }

7. 二叉树的序列化和反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列/反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且这个字符串可以被反序列化得到一个原始的树结构。

例如，你可以序列化下面的二叉树：

得到 "[1,2,3,null,null,4,5]"，这与LeetCode目前使用的方式一致 how LeetCode OJ serializes a binary tree。你并非必须采取这种方式，你也可以创造性的用其他的方式解决这个问题。

小贴士: 不要使用类的成员/全局/静态变量来存储状态机，你的序列化和反序列化算法应该是无状态机的。

思路：

采用层次遍历的方式，每个元素之间“，”隔开，对于null的元素，填充“#”。

LeetCode：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

       // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null){
            return "#,";
        }
        
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        sb.append(root.val).append(",");
        while(!queue.isEmpty()){
            int levelNum = queue.size();
            for (int i = 0; i < levelNum; i++) {
                TreeNode poll = queue.poll();
                
                if(poll.left != null){
                    queue.offer(poll.left);
                    sb.append(poll.left.val).append(",");
                }else{
                    sb.append("#").append(",");
                }
                
                if(poll.right != null){
                    queue.offer(poll.right);
                    sb.append(poll.right.val).append(",");
                }else{
                    sb.append("#").append(",");
                }
                
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        int index = 0;
        TreeNode node = values[index].equals("#") ? null : new TreeNode(Integer.parseInt(values[index]));
        index++;
        if(node == null){
            return null;
        }
        
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(node);
        while(!queue.isEmpty()){
            TreeNode poll = queue.poll();
            poll.left = values[index].equals("#") ? null : new TreeNode(Integer.parseInt(values[index]));
            index++;
            poll.right = values[index].equals("#") ? null : new TreeNode(Integer.parseInt(values[index]));
            index++;
            
            if(poll.left != null){
                queue.offer(poll.left);
            }
            
            if(poll.right != null){
                queue.offer(poll.right);
            }
        }
        return node;
    }
}

8. 先序中序数组结合重构二叉树

给定一棵树的前序遍历与中序遍历，依据此构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 = [3,9,20,15,7]
中序遍历 = [9,3,15,20,7]

返回如下的二叉树：

思路：

先通过前序遍历的第一个元素确定根的元素，然后查找该元素在中序遍历中的位置，采用递归实现。

LeetCode：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null){
            return null;
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }
    public TreeNode buildTree(int[] preorder, int pstart, int pend, int[] inorder, int istart, int iend, HashMap<Integer, Integer> map){
        if(pstart > pend || istart > iend){
            return null;
        }
        
        TreeNode head = new TreeNode(preorder[pstart]);
        int index = map.get(preorder[pstart]);
        
        head.left = buildTree(preorder, pstart + 1, pstart + index - istart, inorder, istart, index - 1, map);
        head.right = buildTree(preorder, pstart + index - istart + 1, pend, inorder, index + 1, iend, map);
        
        return head;
    }
}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
       if(pre == null || in == null){
            return null;
        }
        if(pre.length == 0 || in.length == 0){
            return null;
        }

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

9. 二叉搜索树选出第k个节点

思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。

所以，按照中序遍历顺序找到第k个结点就是结果。

TreeNode KthNode(TreeNode root, int k){
        if(root==null||k==0)
            return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int count = 0;
        TreeNode node = root;
        do{
            if(node!=null){
                stack.push(node);
                node = node.left;
            }else{
                node = stack.pop();
                count++;
                if(count==k)
                    return node;
                node = node.right;
            }
        }while(node!=null||!stack.isEmpty());
        return null;
    }

10. 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)。

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if(root == null){
            return listAll;
        }
        list.add(root.val);
        target = target - root.val;
        if(target == 0 && root.left == null && root.right == null){
            listAll.add(new ArrayList<>(list));
        }
        FindPath(root.left, target);
        FindPath(root.right, target);

        list.remove(list.size() - 1);
        return listAll;
    }
}