二叉树

2021-01-02

二叉树

首先给出二叉树的定义

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

1. 你能遍历二叉树吗

树是一种天然的递归结构，因此涉及到树的问题，大多数可以由递归解决。遍历二叉树最形象的就是递归算法。

//前序遍历
public void preorder(TreeNode root){
	if(root == null)
        return ;
    System.out.println(root.val);
    preorder(root.left);
    preorder(root.right);
}

其他两种遍历方法只需改变函数的调用位置即可。以下设计的主要是非递归算法。这就用到了栈这个数据结构。

1.1 前序遍历

该问题是Leetcode 144号问题。

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

1.2 中序遍历

该问题是Leetcode 94号问题。

public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> ans = new ArrayList<>();
       if(root == null)
           return ans;
       LinkedList<TreeNode> s = new LinkedList<>();
       TreeNode cur = root;
       while(!s.isEmpty()||cur != null){
           while(cur!=null){
               s.push(cur);
               cur = cur.left;
           }
           TreeNode top = s.pop();
           ans.add(top.val);
           cur = top.right;
       }
       return ans;
   }

1.3 后序遍历

这是Leetcode 145号问题，下面介绍的方法其实是利用栈，模拟了函数递归执行的过程。

public static class Command {
       String com;
       TreeNode t;

       Command(String s, TreeNode p) {
           com = s;
           t = p;
       }
   }

   public List<Integer> postorderTraversal(TreeNode root) {
       ArrayList<Integer> ans = new ArrayList<>();
       if(root == null)
           return ans;
       LinkedList<Command> s = new LinkedList<>();
       s.push(new Command("go", root));
       while (!s.isEmpty()) {
           Command top = s.pop();
           if (top.com.equals("print")) {
               ans.add(top.t.val);
           } else {
               s.push(new Command("print", top.t));
               if (top.t.right != null) {
                   s.push(new Command("go", top.t.right));
               }
               if (top.t.left != null) {
                   s.push(new Command("go", top.t.left));
               }
           }
       }
       return ans;
   }

1.4 层次遍历

层次遍历用到了队列这种数据结构。

public List<Integer> levelOrder(TreeNode root) {
       List<Integer> ans = new ArrayList<>();
       if(root == null){
           return ans;
       }
       LinkedList<TreeNode> q = new LinkedList<>();
       q.offer(root);
       while(!q.isEmpty()){
           TreeNode top = q.poll();
           ans.add(top.val);
           if(top.left != null){
               q.offer(top.left);
           }
           if(top.right != null){
               q.offer(top.right);
           }
       }
       return ans;
   }

如果要将每一层的结果保存在一个列表中，该如何？这是Leetcode 102号问题。

//和层次遍历一样，只不过每次都要保存队列的长度
public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> ans = new ArrayList<>();
       if(root == null){
           return ans;
       }
       LinkedList<TreeNode> q = new LinkedList<>();
       q.offer(root);
       while(!q.isEmpty()){
           int len = q.size();
           ArrayList<Integer> tmp = new ArrayList<>();
           for(int i = 0; i < len; i++){
               TreeNode top = q.poll();
               tmp.add(top.val);
               if(top.left != null){
               	q.offer(top.left);
           	}
           	if(top.right != null){
               	q.offer(top.right);
           	}
           }
           ans.add(tmp);
       }
       return ans;
   }

1.5 拓展以及变体

1.5.1 路径总和

这是Leetcode 113号问题。

/**
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。
*/
public List<List<Integer>> pathSum(TreeNode root, int sum) {
       List<List<Integer>> ans = new ArrayList<>();
       if(root == null)
           return ans;
       helper(root, new LinkedList<Integer>(), ans, sum);
       return ans;
   }

   private void helper(TreeNode root , LinkedList<Integer> tmp, List<List<Integer>> ans, int sum){
       if(root.left == null && root.right == null){///叶子节点
           if(root.val - sum == 0){
               tmp.add(root.val);
               LinkedList<Integer> p = (LinkedList<Integer>) tmp.clone();//做一个深拷贝
               ans.add(p);
               tmp.removeLast();//否则，修改tmp会影响到ans里的结果，因为只有一个引用
               return ;
           }else{
               return ;
           }
       }
       tmp.add(root.val);
       if(root.left!=null){
           helper(root.left, tmp, ans, sum - root.val);
       }
       if(root.right!=null){
           helper(root.right, tmp, ans, sum - root.val);
       }
       tmp.removeLast();//回溯
   }

1.5.2 二叉搜索树的最近公共祖先

这是235号问题。主要利用了二叉树的性质。如果查找的两个结点值一个大于根节点值，一个小于根节点值或等于。那么这两个节点分布在根节点两个子树中，最近的结点就是根节点。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     int pval = p.val;
     int qval = q.val;
     int rval = root.val;
     if(rval >= pval && rval <= qval || rval >= qval && rval <= pval){
         return root;
     }
     if(rval < pval && rval < qval){
         return lowestCommonAncestor(root.right,p,q);  
     }else{
         return lowestCommonAncestor(root.left,p,q);
         
     }
 }

1.5.3 二叉树的所有路径

这是Leetcode 257号问题。

/**
给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。
*/
public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> res = new ArrayList<>();
       if (root == null)
           return res;
       // 非递归
       LinkedList<TreeNode> stack = new LinkedList<>();
       stack.push(root);
       LinkedList<String> path = new LinkedList<>();
       path.push(String.valueOf(root.val));
       TreeNode top;
       String p;
       while (!stack.isEmpty()) {
           top = stack.pop();
           p = path.pop();
           if (top.left == null && top.right == null) {
               res.add(p);
               continue;
           }
           if (top.right != null) {
               stack.push(top.right);
               path.push(p + "->" + String.valueOf(top.right.val));
           }
           if (top.left != null) {
               stack.push(top.left);
               path.push(p + "->" + String.valueOf(top.left.val));
           }

       }
       return res;
   }

1.5.4 将有序数组转为二叉搜索树

这是Leetcode 108号问题。这道题关键在于要求转为平衡二叉树。而二分的思想恰好保证了左右子树高度差不超过1 。因为每次除以2，左右两个数组长度最多相差1。

/**
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

*/
public TreeNode sortedArrayToBST(int[] nums) {
       if(nums == null)
           return null;
       return generate(nums, 0, nums.length - 1);//注意边界条件
   }

   private TreeNode generate(int arr[], int start, int end){
       if(start > end)
           return null;
       int mid = (start + end) / 2;
       TreeNode root = new TreeNode(arr[mid]);
       root.left = generate(arr, start, mid-1);
       root.right = generate(arr, mid + 1, end);
       return root;
   }

1.5.5 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。这是Leetcode 98号问题。

//中序遍历的解法，二叉树的中序遍历结果是递增的。
public boolean isValidBST(TreeNode root) {
       if (root == null) {
           return true;
       }
       LinkedList<TreeNode> stack = new LinkedList<>();
       TreeNode cur;
       double preVal = -Double.MAX_VALUE;//存储前一个结点值，如果当前访问的val小于preVal（递减了），返回alse
       while (root != null || !stack.isEmpty()) {
           while (root != null) {
               stack.push(root);
               root = root.left;
           }
           cur = stack.pop();
           if (cur.val <= preVal)
               return false;
           preVal = cur.val;
           root = cur.right;
       }
       return true;
   }

//递归解法 在深搜过程中不断替换最大值和最小值，通过比较根节点值和最大值、最小值从而判定
public boolean isValidBST(TreeNode root){
    return valid(root,Long.MAX_VAK)
}
private boolean valid(TreeNode root,long max, long min){
    if(root == null){
        return true;
    }
    if(root.val > max || root.val < min){
        return false;
    }
    //左子树：最大值为根节点值, 右子树:最小值为根节点值
    return valid(root.left, root.val, min) && valid(root.right, max, root.val);
}

1.5.6 二叉树的最近公共祖先

这是Leetcode 236号问题。

注意：题目给定的是二叉树，不是二叉搜索树。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null && right == null){
            //左右子树中并不包含p、q
            return null;
        }else if(left != null && right != null){
            // 左右子树中包含p、q，则root就是其公共祖先
            return root;
        }else
            return left == null ? right : left;
    }
}

1.5.7 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。这是LeetCode 543号问题。

也是二叉树常用的套路，递归解决。

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

    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        routeLength(root);
        return ans - 1;
    }

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

2. 完全二叉树

2.1 是否是一个完全二叉树

完全二叉树的简单描述就是结点严格按照从上到下、从左到右以此排列，中间不允许出现空结点。因此，算法可以按照定义来编写，利用层次遍历的结果判定。

public static boolean isCBT(TreeNode root) {
       if (root == null)
           return true;
       Queue<TreeNode> queue = new LinkedList<>();
       boolean leaf = false;
       TreeNode L, R, tmp;
       queue.offer(root);
       while (!queue.isEmpty()) {
           tmp = queue.poll();
           L = tmp.left;
           R = tmp.right;
           if (L == null && R != null) {
               return false;
           }
           if (leaf && (L != null || R != null)) {
               return false;
           }
           // 只要左右子树不都存在，leaf标志位就设为true
           if (L != null)
               queue.offer(L);
           if (R != null)
               queue.offer(R);
           else
               leaf = true;
       }
       return true;
   }

2.2 二叉树的结点个数有多少

这是Leetcode 222号问题。

private int countLevel(TreeNode p) {
       if (p == null)
           return 0;
       int depth = 1;
       while (p.left != null) {
           depth++;
           p = p.left;
       }
       return depth;
   }

   public int countNodes(TreeNode root) {
       if(root == null)
           return 0;
       int ans = 1;
       int lheight = countLevel(root.left);
       int rheight = countLevel(root.right);
       if(lheight == rheight){
           ans += (1 << lheight) - 1;//算出左子树
           //递归遍历右子树
           return ans + countNodes(root.right);
       }else{
           ans += (1 << rheight) - 1;
           return ans + countNodes(root.left);
       }
   }

3. 二叉树的性质

3.1 二叉树的深度（高度）

编写一个函数，求二叉树的深度（最大深度）。这是Leetcode 104 号问题。利用递归的思想可以很简单的写出来。

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

3.2 是否是一个平衡二叉树

平衡二叉树的定义是任意左右子树高度差不超过1 。因此，会用到求二叉树深度这个函数。

首先看根节点这棵树左右子树高度差是否超过1，如果是，那么返回false，否则，递归查看左子树、右子树。

这是Leetcode 110号问题。

public boolean isBalanced(TreeNode root) {
       if(root == null){
           return true;
       }
       if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1){
           return isBalanced(root.left) && isBalanced(root.right);
       }else{
           return false;
       }
   }

3.3 交换二叉树的两个节点

这是Leetcode 226 号问题，反转二叉树。还有一个非常有名的互联网段子。

其实，如果已经掌握了二叉树这种递归结构，可以很快的写出代码。

public TreeNode invertTree(TreeNode root) {
       if(root == null)
           return null;
       swap(root);
       return root;
   }
   private void swap(TreeNode root){
       if(root == null)
           return ;
       TreeNode tmp = root.left;
       root.left = root.right;
       root.right = tmp;
       swap(root.left);
       swap(root.right);
   }

3.4 对称二叉树

这是Leetcode 101号问题。

public boolean isSymmetric(TreeNode root) {
       if(root == null){
           return true;
       }
       return judge(root.left, root.right);
       
   }
   private boolean judge(TreeNode left, TreeNode right){
       if(left == null && right == null){
           return true;
       }
       if(left == null || right == null)
           return false;
       if(left.val == right.val){
           return judge(left.left, right.right) && judge(left.right, right.left);
       }else{
           return false;
       }
   }

4. 堆

有关堆的详细介绍参见另一篇博客。

4.1 堆排序

堆排序的最坏时间复杂度和平均复杂度都是 $O(nlogn)$，并且不占用额外的空间。

4.2 优先队列

优先队列底层采用了堆实现。优先队列可以有效解决topK类问题。

采用优先队列的例子，这是Leetcode 451号问题。

class Solution {
    /**
    给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
    
    "tree" -> "eert"
    
    "cccaaa" -> "cccaaa"
    
    首先利用哈希表统计词频，然后构造一个优先队列，队首元素是词频最高的。然后以此将队列中元素出队，就得到一个按照词频由高到低排序的字符串。
    其实是对map按照value进行排序。
    */
    public String frequencySort(String s) {
        TreeMap<Character,Integer> map = new TreeMap<>();
        char ch[] = s.toCharArray();
        for(char c:ch){
           map.put(c,map.getOrDefault(c,0) + 1);
        }

        PriorityQueue<Map.Entry<Character,Integer>> q = new PriorityQueue<>((o1,o2)->{
           if (o1.getValue() == o2.getValue()){
               return o1.getKey().compareTo(o2.getKey());
           }
           return o2.getValue() - o1.getValue();
        });

        for (Map.Entry<Character,Integer> set:map.entrySet()){
            q.offer(set);
        }
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()){
            Map.Entry<Character,Integer> entry = q.poll();
            int times = entry.getValue();
            for(int i = 0; i < times; i++)
                res.append(entry.getKey());
        }
        return res.toString();
    }
}