树的一些算法问题

文章目录

1. 树的一些经典问题
1. 1.1. 判断是否是一棵二叉搜索树

虽然有些事情看的在近期没有什么效果，但是时间久了，终究还是会看出来的，那么你会问，到底什么东西是这样的呢？比如才华、具体到技术来说就是数据结构和算法。
树其实是一种很重要的数据结构，很多重要的算法都是基于这个算法展开的。

树的一些经典问题

判断是否是一棵二叉搜索树

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.

题目分析

读一下题：
其实题目的描述已经很有诚意了,这里直接指出了构成BST的三个特点：

一个节点的左子树的所有（注意，是所有）节点都只会小于该节点
一个节点的右子树的所有节点都只会大于该节点
左、右子树也都必须是BST

大家看出来这个描述有什么特点么？递归的定义方式啊。
所以首先想到的方法会是怎样的？
当然是递归地去判断节点与左右子节点的大小关系，好，这是第一个解法。
还有其他的解法么？
先遍历整个树，然后得到一个数组，然后判断这个数组是否是有序的就可以。
那么现在来实现下面这两个算法：

列出解决想到的方案

首先是递归的：

private boolean isValid(TreeNode node, long max, long min) {
  if (node == null) return true;

  if (node.data >= max || node.data <= min) return false;

  return isValid(node.leftChild, node.data, min) && isValid(node.rightChild, max, node.data);
}

就是根据上面BST的朴素性质来一层层递归判断。注意等于的边界条件。

然后是遍历的

private boolean isValidInNoRecurrenceVersion() {
  // Basic Idea is
  // 1. convert the tree to the array
  // 2. judge the array is in right order?
  if(this.root == null) return true;

  ArrayList theOrderList = new ArrayList();
  theInorderTraversalOrderList(theOrderList);

  // judge the array in the right order(ascend order)
  return isArraySortedInAscendOrder(theOrderList);
}


public boolean isArraySortedInAscendOrder(ArrayList<Integer> list) {
  if (list == null && list.size() == 0) return true;

  int listSize = list.size();
  for (int i = 0; i < listSize - 1; i++) {
    if (list.get(i) > list.get(i+1)){
      return false;
    }
  }

  return true;
}

/**
  *
  * Traversal the tree with the Inorder way
  *
  * @param theInOutList
  */
public void theInorderTraversalOrderList(ArrayList theInOutList) {

  _inOrderTraversal(this.root, theInOutList);
}

private void _inOrderTraversal(TreeNode node, ArrayList theInOutList) {
  Assert.assertNotNull(theInOutList);

  if (node == null) return;

  _inOrderTraversal(node.leftChild, theInOutList);
  theInOutList.add(node.data);
  _inOrderTraversal(node.rightChild, theInOutList);
}

好，我们已经完成了两种实现，下一步就是分析这两种方法的时间空间复杂度。

算法复杂度分析

首先先看下相对简单的递归算法：

时间复杂度
总共三行，前两行的时间复杂度为常数级（O(1)）, 最后一行，返回值行，将这个问题一分为二转化为两个长度为 1/2 的子问题，因此我们有$$T(n) = 2 \cdot O(1) + 2 \cdot T(n/2)$$

因此我们得到结论：该算法的时间复杂度为$O(n^{log_2^2}) = O(n)$

空间复杂度
该算法并未使用额外的辅助空间

其次我们来分析遍历算法：

时间复杂度

整个算法大致可以看作两部分

遍历树得到一个数组
判断该数组是否是一个有序的数组

遍历树的时间复杂度是$O(n)$
判断数组是否为有序数组的时间复杂度也为$O(n)$
那么使用Big-Oh的加法法则有
算法的复杂度为$O(n)$

空间复杂度
该算法用到了一个长度为n的辅助数组

我们当然要选择前者。

好，我们得到了最优的算法，问题就解决了么？
当然……没有！

最优代码优化

我们看下递归算法还可以再有优化的空间么？目前为止还没有看出更简洁的写法了。
好，进入下一步

测试

写出代码，不测试就是耍流氓。

那应该怎样测试这个方法呢？

Happy case
Other case

这里happy case就是构建一个正常的BST，然而other case就是构建一个非BST的二叉树。
说到这里相信你已经看到happy case还好说， other case就有些困难了，需要修改构建树节点的实现，允许构建一个非BST的二叉树，这里就不详细描述算法的细节了，更多的细节移步参考 GitHub工程链接
以及测试工程代码GitHub测试工程链接