算法-二叉树

二叉树

二叉树存储结构

• 二叉链表:设计一个数据域和两个指针域，称这样的链表叫做二叉链表。
• left，right分别是左节点和右节点，value是当前节点的值。

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

二叉树的遍历

• 二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉数中所有结点，使得每个节点被访问一次且仅被访问一次。
  • 访问指的是对该节点存储的值具体做些什么，是一个抽象的操作。

前序遍历

• 规则是若二叉数为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。

中序遍历

• 规则是若数为空，则空操作返回，否则从根节点开始，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树

后序遍历

• 规则是若数为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点

总结：

• 无论是前序遍历，中序遍历还是后续遍历，都是不断递归访问该节点的左右子节点，只是递归处理该节点的顺序不同。
• 前序遍历是在一开始就访问处理该节点的数据，然后递归左边和右边的值。
• 中序遍历是先不断递归该节点左边的节点，直到无左节点，则访问处理该节点数据，然后不断递归访问右节点数据。
• 后续遍历是不断递归访问左节点，然后不断递归访问右节点，直到左右都递归不到节点。则最后访问该节点的值

前序、中序、后序遍历算法

public static void f(Node head){
        if(head == null){
            return;
        }
        /*
        前序遍历
        System.out.println(head.value);
         */
        f(head.left);
        /*
        中序遍历
        System.out.println(head.value);
         */
        f(head.right);
        /*
        后序遍历
        System.out.println(head.value);
         */
    }

层序遍历

• 定义：规则是若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
• 思路：声明一个队列，每次存储他当前层的结点，然后统计数量，然后依次弹出当前层的结点并访问，然后将弹出结点的左右子节点存储到队列中，依次进行上述操作，直到当前队列为空

public class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> ans = new LinkedList<>();
    if(root == null){
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        int size = queue.size();
        List<Integer> curAns = new LinkedList<>();
        for(int i = 0;i<size;i++){
            TreeNode curNode = queue.poll();
            curAns.add(curNode.val);
            if(curNode.left !=null){
                queue.add(curNode.left);
            }
            if(curNode.left != null){
                queue.add(curNode.right);
            }
        }
        ans.add(curAns.val);//自上而下的层序遍历
        //ans.add(0,curAns.val);//自下而上的层序遍历
    }
    return ans;
}

---

相关算法题

1. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路：其实就是递归访问每个节点，只要有一个节点的值不相同，或者位置相同，但是一个有节点，一个没有节点，那就是不相同的树,用前序，中序，后序遍历都可以，只要将打印的操作替换成访问操作即可

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

public static boolean isSameTree(TreeNode p,TreeNode q){
    if(p == null ^ q ==null){
        return false;
    }
    if(p == null && q == null){
        return true;
    }
    return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

---

2.对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

• 思路：其实依旧是遍历当前树上的所有的节点，只是把他当成两颗不同的树，一个访问左节点，一个访问右节点。根节点是同一个根节点，与上面相同的树思路差不多。

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

public static boolean isSymmetric(TreeNode root){
    return isMirror(root,root);
}

public static boolean isMirror(TreeNode p,TreeNode q){
    if(p == null ^ q ==null){
        return false;
    }
    if(p == null && q == null){
        return true;
    }
    return p.val = q.val && isMirror(p.left,q.right) && isMirror(p.right,q.left);
}

---

3.二叉树的最大深度

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

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

说明: 叶子节点是指没有子节点的节点。

思路：依次访问该节点的左节点和右节点，分别返回左节点和右节点的当前深度，然后挑选一个最大值+1，返回给到上一层的节点，直到最顶层

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

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

4.从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1. 首先递归访问二叉树，就是递归创建二叉树。
2. 可以理解为我通过先序遍历的数组a，能得到第一个根节点-pre[0]，并创建该节点
3. 然后通过pre[0]创建根节点，再通过中序遍历的数组，确定当前根节点的左右节点树，进而可以推断出来前序遍历数组的左右根节点范围
4. 然后在将前序遍历的左树范围和中序遍历的左树范围按上述方法继续确定当前左树的根节点，直到递归到当前节点没有左树，就结束当前递归，转而递归寻找当前节点的右树
5. 右树的递归创建过程与左树类似
6. 创建一个hashMap，用来记录中序遍历当前数组值的位置，可以快速获得前序遍历根节点在中序遍历数组中的位置。

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val = val;
    }
}

public TreeNode buildTree(int[] preorder, int[] inorder){
    if(preorder != null || inorder != null || preorder.length != inorder.length){
        return null;
    }
    Map<Integer,Integer> valueIndexMap = new HashMap<>();
    for(int i = 0;i < inorder.length;i++){
        valueIndexMap.put(inorder[i],i);
    }
    
    return g(preorder,0,preorder.length-1,inorder,0,inorder.length-1,valueIndexMap);
}

public TreeNode g(int[] pre,int L1,int R1,int[] in,int L2,int R2,Map<Integer,Integer> valueIndexMap){

    /*
    L1 > R1:表明当前节点只有左树，或者只有右树
    */
    if(L1 > R1){
        return null;
    }
    //前序数组的L1必定是当前树的根节点
    TreeNode head = new TreeNode(pre[L1]);
    //当前节点没有子节点
    if(L1 == R1){
        return head;
    }
    //找到当前节点在中序数组中的位置
    int find = valueIndexMap.get(pre[L1]);
    //左树的长度是中序遍历：find - L2，因此推的R1=L1 + find - L2
    head.left = g(pre,L1+1,L1 + find - L2,in,L2,find-1,valueIndexMap);
    //右树的L1就是当前节点左树范围的R1+1,因此推的L1= R1 + 1 = L1 + find - L2 + 1
    head.right=g(pre,L1+find-L2+1,R1,in,find+1,R2,valueIndexMap);
    return head;
}

---

5.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

思路：声明一个全局变量isSum = false,对每个节点前序遍历访问，访问之前，判断该节点是否满足左右叶子均为空，如果为空，说明该线路是一条路径。把该线路上的节点的值的和与targetSum进行判断，如果相等，说明存在，则返回true

public class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

public boolean isSum = false //全局变量 默认为负

public boolean hasPathSum(TreeNode root, int targetSum) {
	if(root == null){
        return false;
    }
    isSum = false;
    process(root,0,targetSum);
    return isSum;
}

public static void process(TreeNode x,int preSum,int sum){
    if(x.left == null && x.right == null){
        if(preSum + x.val == sum){
            isSum = true;
        }
        return;
    }
    preSum += sum;
    if(x.left != null){
        process(x.left,preSum,sum);
    }
    /**
    如果该节点的左节点已经找到路径，那就不用寻找，直接推出该节点即可
    */
    if(!isSum){
        return;
    }
    if(x.right != null){
        process(x.right,preSum,sum);
    }
}

6.路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

思路：声明一个数组ans保存当前满足targetSum的路径，在声明一个数组path保存当前经过的节点的val值，每次访问该节点，先将该节点的值保存进路径中，然后依次访问左右节点，直到路径到头，判断，如果是targetSum，就把当前path放进ans中，然后path删除当前节点，返回上一节点，直到所有节点全部前序遍历访问完

public class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

public static List<Integer> copy(List<Integer> path){
    List<Integer> ans = new ArrayList<>();
    for(Integer num : path){
        ans.add(num);
    }
    return ans;
}

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
	if(root == null){
        return null;
    }
    List<List<Integer>> ans = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    
}

public static void process(TreeNode x,List<Integer> path,int preSum,int sum, List<List<Integer>> ans){
    if(x.left == null && x.right == null){
        if(preSum + x.val == sum){
            path.add(x.val);
            ans.add(copy(path));
            path.remove(path.size() -1);
        }
        return;
    }
    
    preSum += x.val;
    path.add(x.val);
    if(x.left != null){
        process(x.left,path,preSum,sum,ans);
    }
    if(x.left != null){
        process(x.right,path,preSum,sum,ans);
    }
    path.remove(path.size() -1);
}

---

平衡二叉树

定义：平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1

平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

输入：root = [3,9,20,null,null,15,7]
输出：true

思路：声明一个节点信息，记录当前节点是否是平衡二叉树以及当前节点的高度。并返回给上一个节点，然后上一个节点接收到左右两节点的信息，进而能判断自己是否是平衡节点

public class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val = val;
    }
}

public Info {
    public boolean isBalanced;
    public int height;
    
    public Info(boolean i,int h){
        this.isBalanced = i;
        this.height = h;
    }
}

public boolean isBalanced(TreeNode root){
    
}

public static Info process(TreeNode root){
    if(root == null){
        return new Info(true,0);
    }
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    int height = Math.max(leftInfo.height,rightInfo.height)+1;
    boolean isBalanced = leftInfo.isBalanced 
        				&& rightInfo.isBalanced 
        				&& Math.abs(leftInfo.height - rightInfo.height) < 2;
    return new Info(isBalanced,height);
}

---

搜索二叉树

定义：

• 二叉排序树(Binary Sort Tree),又称为二叉查找树，它或者是一颗空树，或者是具有下列性质的二叉树
  1. 若他的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
  2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3. 它的左，右子树也分别为二叉排序树

判断是否是搜索二叉树

• 思路：根据定义：可以判断他的左右两结点是否也满足BST，并且左树的最大值要小于当前节点的值，右树的最小值要大于当前节点的值。

public class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}

public class Info{
    public boolean isBST;
    public int max;
    public int min;
    public Info(boolean is, int ma, int mi){
        this.isBST = is;
        this.ma = max;
        this.mi = min;
    }
}

public static Info process(TreeNode x){
    if(x == null){
        return null;//没有节点，返回空信息
    }
    
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int max = x.val;
    int min = x.val;
    if(leftInfo != null){
        max = Math.max(max,leftInfo.max);
        min = Math.min(min,leftInfo.min);
    }
    if(rightInfo != null){
        max = Math.max(max,rightInfo.max);
        min = Math.min(min,leftInfo.min);
    }
    boolean isBST = false;
    boolean leftBST = leftInfo == null ? true : leftInfo.isBST;
    boolean rightBST = rightInfo == null ? true : rightInfo.isBST;
    boolean leftMAXLessX = leftInfo == null ? true : (leftInfo.max < x.val);
    boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
    if(leftBST && rightBST && leftMaxLessX && rightMinMoreX){
        isBST = true;
    }
    return new Info(isBST,max,min);
}

---

小顶堆

定义

• 堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左子节点和右子节点的值。

• 最大堆和最小堆是二叉堆的两种形式：

• 最大堆：根结点的键值是所有堆结点键值中最大者。

  最小堆：根结点的键值是所有堆结点键值中最小者。

相关算法

合并k个升序列表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

思路：用小顶堆或者TreeMap都能实现该功能，因为只需要每次取出该数据的时候满足是当前各个链表节点的最小值即可

public static class ListNode {
	public int val;
	public ListNode next;
}

public static ListNode mergeLists(ListNode[] lists) {
     if (lists == null) {
         return null;
     }
     PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
         @Override
      public int compare(ListNode o1, ListNode o2) {
         return o1.val - o2.val;
         }
     });
     for (int i = 0; i < lists.length; i++) {
         if (lists[i] != null) {
         heap.add(lists[i]);
         }
     }

     if (heap.isEmpty()) {
         return null;
     }

     ListNode head = heap.poll();
        ListNode pre = head;
     while (!heap.isEmpty()) {
        ListNode cur = heap.poll();
        pre.next = cur;
        pre=cur;
        if(cur.next != null){
            heap.add(cur.next);
        }
     }
     return head;
  }