树—最“有套路”的数据结构

03/01 09:19
阅读数 30

前言

标题用“有套路”来形容一种数据结构,似乎有点不尊重的意思。不过,我倒是觉得,一种实用的学科,就是应该产生一点套路,这才能发挥体系化研究的优势,套路就是一种保证:在不投入更多创造性与努力的情况下,依旧能获得比起随意进行相关操作更好的结果。一门成熟的学科都应如是,如果研究许久,在学科所研究的许多问题的实践上还不如一些“天赋”“灵感”,那就不得不说这门学科的“伪科学”或者“水分”还是蛮大的了。

言归正传,这篇文章将会是一系列寻找算法与数据结构的文章的开篇,树由于其特性,是递归、分治等等重要算法思想的典型载体,同时套路性较强又具有一定规律和难度,上手后,也可以获得总结其他算法“套路”的必要经验。作为一个训练的开头,还是很合适了。

树的定义与理解

先简要谈谈树的抽象定义:树本质上是一种无向图(图:由顶点与路径构成的数据结构),其中,任意两个顶点之间有且只有一条路径。简而言之,树是一种具有特殊性质的图。

树的结构非常直观,而且树的大多数结构具有一个重要性质:递归。主要来说,就是树具有某一性质时,往往其子树也具有同样的性质。比如说,一个树如果是二叉搜索树,其子树也必须是二叉搜索树。

根据这样的性质,遇到树的问题,很自然会考虑如何合理使用递归算法,其实质就是:分解为子问题,最后解决基本情况,把复杂的递归过程交给计算机来处理。所以,树类型代码的特点就是简洁(不过换句话说,由于太简洁,很多思维过程又交给了计算机,有时候写对了没有都不知道:) )

所以,面试官往往是在用树来考察你对递归算法的理解。

一般来说,树具有以下可能的形状: 普通二叉树、平衡二叉树(即叶子节点的深度相差不超过1)、完全二叉树(除了最后一层外,每层节点全部填满,最后一层若不满,必须是右边的节点缺少;每层都填满的,被称为完美二叉树)、四叉树(quadtree,即每个节点最多有四个孩子)、N叉树(每个节点最多有N个孩子)。

树的遍历

先谈谈为什么要遍历。其实对于一个数据结构的基础算法(不讨论那些奇技淫巧),重要的不过增查改删(CRUD)。对于树这样一个结构,在没有先验知识的情况下,为了使得代码量可控,考虑到树的结构是固定的(或者说每个节点/子树都具有一样的结构),我们就得依照其连接关系借助递归方法,以一种特定的顺序进行访问。当全部的节点都被访问时,这样的操作就是一个遍历。

前序遍历(pre-order traversal):

访问顺序:根-左子树-右子树

简单实现代码:

1public void preorderTraverse(TreeNode root){
2  visit(root); // 此步执行遍历的功能,比如说打印、比较、存储等等
3  preorderTraverse(root.left);
4  preorderTraverse(root.right);
5}

应用场景:在树中进行搜索、创建一棵新的树(没有根,左右子树创建后不便于连接)。

中序遍历(inorder Traverse)与后序遍历(postorder Traverse):

基本同前序遍历,只是顺序上,中序是左-根-右,后序是左-右-根。

中序遍历可写作这样的递归形式:

1public void inorderTraverse(TreeNode root){
2  inorderTraverse(root.left);
3  visit(root); // 此步执行遍历的功能,比如说打印、比较、存储等等
4  inorderTraverse(root.right);
5}

可以看到,此时也并不复杂,只是单纯地换序而已,将在根处的操作移动到了中间,规律明显,代码也易于阅读。

对于中序遍历,其应用场景最常见的是二叉搜索树,按这样的顺序遍历出来,输出的结果是按大小顺序的(比如说递增)。

关于后序遍历,如果在对某个节点进行分析时,需要其左右子树的信息(大小、存在与否等等),那么可以考虑后序遍历,仿佛就是在修剪一棵树的叶子,可以从外向内不断深入修剪。

由于三种遍历说的前中后都是针对根节点,国内也有教材把上述遍历方式称为,先根遍历中根遍历后根遍历,前中后决定的只是根的位置,左子树都在右子树之前,这样记忆可能简单些(虽然最好的记忆方法永远是实现几个代码)。

不过,递归写法虽然容易,非递归写法也需要掌握。

这里提供一种前序遍历的非递归写法的分析思路:

主要考虑用栈来模拟上面的递归(递归本质上也是操作系统/OS在帮你压栈,所以递归深度过深时报错也是所谓“stack overflow”,即栈溢出):

以下出自leetcode144题,即二叉树前序遍历:

 1public List<Integer> preorderTraversal(TreeNode root){
2  List<Integer> res = new ArrayList<>(); // 用于保存遍历结果
3  Stack<TreeNode> stack = new Stack<>();
4  TreeNode curr = root; // 用于指示当前节点
5  while(curr != null || !stack.isEmpty()){
6        if(curr != null){
7      res.add(curr.val);
8        stack.push(curr);
9        curr = curr.left; // 考虑左子树
10    } else{
11      // 节点为空,弹栈,回溯到上一层
12      curr = stack.pop();
13      // 此时考虑右子树
14      curr = curr.right;
15    }
16  }
17  return res;
18}

类似地,中序遍历可以写作以下非递归形式,除了稍微改变顺序以外,几乎跟前序遍历一样:

 1public List<Integer> inorderTraversal(TreeNode root) {
2        List<Integer> res = new ArrayList();
3        Stack<TreeNode> stack = new Stack();
4        TreeNode curr = root; // 指示当前位置
5
6        while(curr != null || !stack.isEmpty()){
7            if(curr != null){
8                stack.push(curr); 
9                curr = curr.left;  //先入栈,并指向左节点
10            } else{
11                //当前节点为空时,出栈,并进行操作,随后指向右节点
12                curr = stack.pop();
13                res.add(curr.val);
14                curr = curr.right;
15            }
16        }
17
18        return res;
19    }

不同于上面两个,后序遍历的非递归略微难写一点,主要是因为需要考虑根节点的问题,在整个遍历过程中,根节点会被访问两次,需要判断是否右子树已经被访问过了,才能确认根节点是否需要被保存。最简单粗暴的想法就是用hashset保存已经访问过的节点:

 1class Solution {
2    public List<Integer> postorderTraversal(TreeNode root) {
3        List<Integer> res = new ArrayList();
4        Stack<TreeNode> stack = new Stack();
5        Set<TreeNode> set = new HashSet<>();
6        TreeNode curr = root;
7
8        while(curr != null || !stack.isEmpty()){
9              // 首先不断向左子树运动
10            while(curr != null && !set.contains(curr)){
11                stack.push(curr);
12                curr = curr.left;
13            }
14              // 此时不能直接保存根节点再去右子树,所以只能利用peek来寻找右子树
15            curr = stack.peek();
16              // 若右子树为空,或者已经访问过一次这个节点,可以弹出
17            if(curr.right == null || set.contains(curr)){
18                res.add(curr.val);
19                set.add(curr);
20                stack.pop();
21                  // 若栈此时已经弹空,可以返回结果
22                if(stack.isEmpty()){
23                    return res;
24                }
25                curr = stack.peek();
26                curr = curr.right;
27            } else{
28                  // 若不然,先向右移动,保存该点到hashset中确认已经访问过一次
29                set.add(curr);
30                curr = curr.right;
31            }
32        }
33        return res;
34    }
35}

上述解法是利用hashset来保存根节点是否已经被越过一次,但是重要的其实只是确认根节点的右子树是否被访问过,所以只需要知道上一个节点是不是其右子树就行,因此保留一个上一个节点的变量即可:

 1class Solution {
2    public List<Integer> postorderTraversal(TreeNode root) {
3                 List<Integer> res = new ArrayList();
4          Stack<TreeNode> stack = new Stack();
5          TreeNode curr = root;
6          TreeNode pre = null;
7
8          while(curr != null || !stack.isEmpty()){
9              if(curr != null){
10                  stack.push(curr);
11                  curr = curr.left;
12            } else{
13                  TreeNode temp = stack.peek();
14                  // 考虑是否变为右子树
15                  if(temp.right != null && temp.right != pre){
16                      curr = temp.right;
17                } else{
18                      res.add(temp.val);
19                      pre = temp;
20                      stack.pop();
21                }
22            }
23        }
24          return res;
25    }
26}

官方题解的方法则更为巧妙一点,即考虑将相关的内容逆序保存,这样巧妙地规避了根节点不便处理的问题:实现一个右、左、中的保存顺序,实现时还是按中、右、左来进行,保存数字时逆序。

利用了LinkedList特有的addFirst方法,将新出现的数值插入到链表的开头,同事时,由于stack的顺序是先进后出,所以看似是中、左、右,出栈后又是中、右、左,由于保存的顺序是每次加入到链表开头,所以实际上进行了一个逆序,完成了一个左、右、中的过程:

 1class Solution {
2  public List<Integer> postorderTraversal(TreeNode root) {
3    LinkedList<TreeNode> stack = new LinkedList<>();
4    LinkedList<Integer> output = new LinkedList<>();
5    if (root == null) {
6      return output;
7    }
8
9    stack.add(root);
10    while (!stack.isEmpty()) {
11      TreeNode node = stack.pollLast();
12      output.addFirst(node.val);
13      if (node.left != null) {
14        stack.add(node.left);
15      }
16      if (node.right != null) {
17        stack.add(node.right);
18      }
19    }
20    return output;
21  }
22}

除了使用那么复杂的办法,也有一种“投机取巧”的办法,就是先做中-右-左的遍历,然后把遍历结果逆序,也就得到了后序遍历结果了。修改我们上面出现过的前序遍历代码也不难得到类似结果:

 1public List<Integer> postorderTraversal(TreeNode root){
2  List<Integer> res = new ArrayList<>(); // 用于保存遍历结果
3  Stack<TreeNode> stack = new Stack<>();
4  TreeNode curr = root; // 用于指示当前节点
5  while(curr != null || !stack.isEmpty()){
6        if(curr != null){
7      res.add(curr.val);
8        stack.push(curr);
9        curr = curr.right; // 考虑右子树
10    } else{
11      // 节点为空,弹栈,回溯到上一层
12      curr = stack.pop();
13      // 此时考虑右子树
14      curr = curr.left;
15    }
16  }
17  Collections.reverse(res); // 直接使用内置的逆序,不必在插入时一一进行操作
18  return res;
19}

当然,如果要多做一点优化,可以模仿前一个结果,在添加到res时使用addFirst方法。对于java实现,这里有一个小细节,在声明时,必须使用LinkedList,因为List不提供addFirst方法接口。

经典例题回顾:

讲了基本的定义与三个遍历的递归与非递归写法,其实树的基础知识已经足够了,基本上遇到题目稍做变化就行了,不信?直接上一些看似复杂的题目看看吧。

leetcode250题(后序遍历):统计有多少个子树拥有相同的数字。

Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
给定一个二叉树,统计其uni-value子树的个数。
一个uni-value子树指的是这个子树的全部节点的值相同。

一段有问题的代码(对于测试样例[5,1,5,5,5,null,5],正确答案4,输出结果2):

 1class Solution {
2    int count = 0;
3    public int countUnivalSubtrees(TreeNode root) {
4        postorder(root); // 从根节点开始遍历
5        return count;
6    }
7
8    public boolean postorder(TreeNode root){
9        if(root == null) return true;
10        if(postorder(root.left) && postorder(root.right)){
11            if(root.left != null && root.left.val != root.val) return false;
12            if(root.right != null && root.right.val != root.val) return false;
13            count++;
14            return true;
15        }
16        return false;
17    }
18}

可通过的代码:

 1class Solution {
2    int count = 0;
3    public int countUnivalSubtrees(TreeNode root) {
4        postorder(root);
5        return count;
6    }
7
8    public boolean postorder(TreeNode root){
9        if(root == null) return true;
10        if(postorder(root.left) & postorder(root.right)){
11            if(root.left != null && root.left.val != root.val) return false;
12            if(root.right != null && root.right.val != root.val) return false;
13            count++;
14            return true;
15        }
16        return false;
17    }
18}

在完成这题的过程中,我犯了一些错误,主要在于没有深刻理解递归:

  1. 在使用判断条件postorder(root.left)以及postorder(root.right)时,实际上已经发生了递归;(所以假定这题是前序遍历或中序遍历会很难完成代码的构造)
  2. 在java中,使用&&会出现短路,即前半部分已经false了之后,会自动不执行后半部分,因此为了逻辑的正确,此处只能使用&。

leetcode230题:

求在二叉搜索树(BST)中第k小的值,本题主要考虑使用中序遍历,因为二叉搜索树中序遍历是一个递增的数列:

唯一需要注意的就是左子树遍历完成后,有可能还没有达到k,那么可以设定Integer.MAX_VALUE作为没有找到的标志,防止未找到。

这个算法遍历的时间空间复杂度是O(k),最坏的情况下有可能达到O(N)。(在leetcode平台上打败了100%的java程序)

 1class Solution {
2    int count = 0;
3    public int kthSmallest(TreeNode root, int k) {
4        if(root.left != null){
5            int res = kthSmallest(root.left, k);
6            if(res != Integer.MAX_VALUE) return res; // 若未能寻找到,应继续向右搜索
7        } 
8        count++;
9        if(count == k) return root.val;
10        if(root.right != null) return kthSmallest(root.right, k); // 题目中保证了能搜索到,所以此处不必再加判断
11
12        return Integer.MAX_VALUE; // 若在左侧节点未寻找到,返回这个标志
13    }
14}

相比之下,官方题解则先将全部的节点遍历到一个数组中,然后再寻找第k个,问题就在于将时间复杂度因而扩大到了O(N)。(使用这个方法,时间上只能打败49.01%的程序)

 1class Solution {
2  public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> arr) {
3    if (root == null) return arr;
4    inorder(root.left, arr);
5    arr.add(root.val);
6    inorder(root.right, arr);
7    return arr;
8  }
9
10  public int kthSmallest(TreeNode root, int k) {
11    ArrayList<Integer> nums = inorder(root, new ArrayList<Integer>());
12    return nums.get(k - 1);
13  }
14}

leetcode366题:

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

给定一个二叉树,返回一个树的节点的集合的集合,每次都收集并移除当前的所有的叶子节点,直到整个树为空。

这是一个很有趣的题目,因为如果从上向下遍历,是不难的,直接使用BFS(宽度优先搜索),这样的方式又叫“层次遍历”(level-order traversal);然而,从下往上则无这个顺序,左右子树的深度非常有可能不同,而叶子节点只需要左右子树不存在即可。

本题可采用了刚才所谓的“剥洋葱”的办法,因此可以先考虑后序遍历(本题算是一种变体):

 1class Solution {
2    public List<List<Integer>> findLeaves(TreeNode root) {
3        List<List<Integer>> res = new ArrayList();
4          while(root != null){
5              List<Integer> curr = new ArrayList();
6              root = upward(root, curr);
7              res.add(curr);
8        }
9          return res;
10    }
11
12      public TreeNode upward(TreeNode root, List<Integer> curr){
13          // 函数的功能是将所有叶子节点保存到curr中,然后把叶子节点置为null
14          if(root == null) return null;
15          if(root.left == null & root.right == null){
16              // 如果是叶子节点,加入curr,然后返回null
17              curr.add(root.val);
18              return null;
19        }
20          // 如果不是叶子节点,递归调用其左右子树,保存新的情况
21          root.left = upward(root.left, curr);
22          root.right = upward(root.right, curr);
23          return root;
24    }
25}

这一题算是使用了一种变体方法,不过本质上还是一种后序遍历。

当然,这题也可以不修改树,直接考虑DFS(深度优先搜索)再回溯,但是就需要引入一个判断深度的指标来进行控制了:

 1class Solution {
2    public List<List<Integer>> findLeaves(TreeNode root) {
3        List<List<Integer>> res = new ArrayList();
4          postorder(root,res);
5          return res;
6    }
7
8      public int postorder(TreeNode root, List<List<Integer>> res){
9          if(root == null) return -1; // 空节点置为-1,因为叶子节点是0
10          // 递归调用获取当前深度(准确的说,其实是从叶子节点开始的高度)
11          int depth = 1 + Math.max(postorder(root.left,res),postorder(root.right,res));
12          // 根据java语法,如果还没有list对象,需要先创建
13          if(depth >= res.size()) res.add(new ArrayList());
14          // 将节点加入对应深度,由于递归必然从最深处开始,顺序不会有问题
15          res.get(depth).add(root.val);
16          return depth;
17    }
18}

leetcode285:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node p is the node with the smallest key greater than p.val.

给定一个二叉搜索树,并给定一个节点,寻找这个节点的中序遍历的后续节点。

寻找二叉搜索树的中序遍历后继,可以从递归和迭代两种方法完成,由于已经暗示明白了,直接使用中序遍历即可解决这一问题:

递归法依旧有容易阅读的优点,不过构造时不必想太复杂,直接使用前序节点来保存前一个数据即可。(此时已经达到了不错的结果,时间达到了92%)

 1class Solution {
2    TreeNode pre = null;
3    TreeNode ans = null;
4    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
5        if(root == null || p == null) return null;
6        inorderSuccessor(root.left, p);
7        if(pre == p){ // 条件也可改为 pre != null && pre.val == p.val
8              // 如果其前继节点已经满足条件,则保存结果
9            ans = root;
10        }
11        pre = root;
12        inorderSuccessor(root.right,p);
13        return ans;
14    }
15}

非递归方法:这一方法直接改自中序遍历,不过实际上没有充分利用BST暗含的规律,所以速度不是最快的,仅仅达到了28.88%。

 1class Solution {
2    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
3        if(curr == null || p == null) return null;
4          Stack<TreeNode> stack = new Stack();
5          TreeNode curr = root;
6          boolean foundP = false;
7          while(root != null || !stack.isEmpty()){
8              if(curr != null){
9                  stack.push(curr);
10                  curr = curr.left;
11            } else{
12                  curr = stack.pop();
13                  if(foundP == true){
14                      return curr;
15                }
16                  if(curr.val == p.val){
17                      foundP = true;
18                }
19                  curr = curr.right;
20            }
21        }
22          return null;
23    }
24}

不得不说,使用遍历来解决树问题,实在是颇有“一招鲜吃遍天”的感觉,甚至略加改进就能解决hard级的leetcode99题。

leetcode99题:

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

一个二叉搜索树的两个元素被交换了。

复原这个树,使得它符合BST结构,但不改变树的整体结构。

这题就是恢复二叉搜索树的问题。看到BST,几乎是一个中序遍历的问题。本题需要注意的地方就是,被交换的节点存在两种可能性,一种是相邻节点的顺序反了,那么,直接交换值即可,另外一种是相隔的节点顺序错了,因此还需要保存第二次发生前序节点大于当前节点的位置。(以下主要由中序遍历模板改出)

非递归:

 1class Solution {
2    public void recoverTree(TreeNode root) {
3        Stack<TreeNode> stack = new Stack();
4        TreeNode prev = null, curr = root;
5        TreeNode first = null, second = null; // 用于保存改变的第一个和第二个位置
6
7        while(curr != null || !stack.isEmpty()){
8            if(curr != null){
9                stack.push(curr);
10                curr = curr.left;
11            } else{
12                curr = stack.pop();
13                  // 如果发生了前序节点大于当前节点,分两种情况
14                if(prev != null && prev.val > curr.val){
15                      // 如果是第一次遇到,保存first为前序,second为当前
16                    if(first == null){
17                        first = prev;
18                        second = curr;
19                    } else{
20                          // 如果第二次遇到,只重新保存当前值到second中
21                        second = curr;
22                    }
23                }
24                prev = curr;
25                curr = curr.right;
26            }
27        }
28        int temp = first.val;
29        first.val = second.val;
30        second.val = temp;
31    }
32}

递归:

 1class Solution {
2    TreeNode first = null;
3    TreeNode second = null;
4    TreeNode prev = null;
5    public void recoverTree(TreeNode root) {
6        inorder(root);
7        int temp = first.val;
8        first.val = second.val;
9        second.val = temp;
10    }
11
12    public void inorder(TreeNode root){
13        if(root == null) return;
14        inorder(root.left);
15          // 对前序节点进行判断
16        if(prev != null && prev.val > root.val){
17              // 第一次遇到则全部保存
18            if(first == null){
19                first = prev;
20                second = root;
21            } else{
22                  // 第二次遇到只保存second
23                second = root;
24            }
25        }
26          // 更新prev节点
27        prev = root;
28        inorder(root.right);
29    }
30}

简要总结

树的题目大多来自三种遍历的变体,一般而言,稍作一些修改就能得到一个能运行的结果(实在不行先全部遍历一遍保存到数组里来解决);不过,为了得到最优解,往往还需要根据题目已有的一些条件或者性质,对递归进行一些优化(如结束递归的条件,递归的方式等等);有时递归不便于进行一些细节操作时,可以考虑用非递归写法(当然,由于递归写法解题有时太轻松,出于面试难度问题,面试官也往往会要求非递归,也算是为学习非递归多一个理由吧!)。

原文出处:https://www.cnblogs.com/mingyu-li/p/12388360.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部