算法通关 - 树&二叉树&二叉搜索树

树（Tree）

树是n (n>=0) 个节点的有限集。当n=0时，称为空树。在任意一个非空树下，有如下特点：

有且仅有一个特定的称为根的节点
当n>1时，其余节点可以分为m(m > 0) 个互不相交的有限集，每一个集合本身又是一个树，并成为根的子树

二叉树（Binary Tree）

二叉树是树的一种特殊形式，二叉树的每个节点最多有两个孩子节点。注意，这里是最多由两个，也可能只有一个，或者没有孩子节点。二叉树节点的两个孩子节点，一个被称为左孩子，一个被称为右孩子。

二叉树还有两种特殊的形式，一种是满二叉树，一种是完全二叉树。

一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。简单说，满二叉树的每个分支都是满的。

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。完全二叉树条件没有满二叉树那么苛刻，满二叉树要求所有分支都是满的，而完全二叉树只需保证最后一个节点之前的节点都齐全即可。

//常用的二叉树的实现
public class TreeNode{
  public int val;
  public TreeNode left,right;
  public TreeNode(int val){
    this.val = val;
    this.left = null;
    this.right = null;
  } 
}

二叉搜索树（Binary Search Tree）

二叉查找树.png

二叉搜索树又称二叉排序树(sorted binary tree)、有序二叉树(ordered binary tree)，是指一棵空树或者具有下列性质二叉树。

左子树上所有节点的值均小于它的根节点的值
右子树上所有节点的值均大于它的根节点的值
左右子树也都是二叉查找树

简单理解：链表就是特殊化的树，树就是特殊化的图。链表其实是每一个节点有一个指针指向下一个节点，而树则可以理解为每个节点可以有多个指针指向其他节点。

各种数据结构的时间复杂度

各种数据结构时间复杂度.png

1.验证二叉搜索树（LeetCode - 98）

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

示例:
输入:
    2
   / \
  1   3
输出: true

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

方法一：递归。将结点的值与上界和下界（如果有）比较。然后，对左子树和右子树递归进行该过程。

//定义二叉树节点
public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

class Solution {
  public boolean helper(TreeNode node, Integer lower, Integer upper) {
    if (node == null) return true;

    int val = node.val;
    if (lower != null && val <= lower) return false;
    if (upper != null && val >= upper) return false;

    if (! helper(node.right, val, upper)) return false;
    if (! helper(node.left, lower, val)) return false;
    return true;
  }

  public boolean isValidBST(TreeNode root) {
    return helper(root, null, null);
  }
}

时间复杂度 : O(N)。每个结点访问一次。
空间复杂度 : O(N)。我们跟进了整棵树。

方法二：迭代。使用栈，上面的递归法可以转化为迭代法。这里使用深度优先搜索，比广度优先搜索要快一些。

class Solution {
  LinkedList<TreeNode> stack = new LinkedList();
  LinkedList<Integer> uppers = new LinkedList(),
          lowers = new LinkedList();

  public void update(TreeNode root, Integer lower, Integer upper) {
    stack.add(root);
    lowers.add(lower);
    uppers.add(upper);
  }

  public boolean isValidBST(TreeNode root) {
    Integer lower = null, upper = null, val;
    update(root, lower, upper);

    while (!stack.isEmpty()) {
      root = stack.poll();
      lower = lowers.poll();
      upper = uppers.poll();

      if (root == null) continue;
      val = root.val;
      if (lower != null && val <= lower) return false;
      if (upper != null && val >= upper) return false;
      update(root.right, val, upper);
      update(root.left, lower, val);
    }
    return true;
  }
}

时间复杂度 : O(N)。
空间复杂度 : O(N)。

方法三：中序遍历

class Solution {
  public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack();
    double inorder = - Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // If next element in inorder traversal
      // is smaller than the previous one
      // that's not BST.
      if (root.val <= inorder) return false;
      inorder = root.val;
      root = root.right;
    }
    return true;
  }
}

时间复杂度 : 最坏情况下（树为二叉搜索树或破坏条件的元素是最右叶结点）为O(N)。

空间复杂度 : O(N) ，用于存储 stack。

2.二叉搜索树的最近公共祖先（LeetCode - 235）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

方法一：递归。

1.从根节点开始遍历树

2.如果节点 p 和节点 q 都在右子树上，那么以右孩子为根节点继续 1 的操作

3.如果节点 p 和节点 q 都在左子树上，那么以左孩子为根节点继续 1 的操作

4.如果条件 2 和条件 3 都不成立，这就意味着我们已经找到节 p 和节点 q 的 LCA 了

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        //当前节点或者是根节点的值
        int parentVal = root.val;
        //节点p的值
        int pVal = p.val;
        //节点q的值
        int qVal = q.val;

        if (pVal > parentVal && qVal > parentVal) {
            // 如果p和q的值都比parentVal大
            return lowestCommonAncestor(root.right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            // 如果p和q的值都比parentVal小
            return lowestCommonAncestor(root.left, p, q);
        } else {
            //我们找到最近公共祖先了，就是当前root节点
            return root;
        }
    }
}

时间复杂度：O(N)
其中 N 为 BST 中节点的个数，在最坏的情况下我们可能需要访问 BST 中所有的节点。
空间复杂度：O(N)

所需开辟的额外空间主要是递归栈产生的，之所以是 N 是因为 BST 的高度为 N。

方法二：迭代。

我们用迭代的方式替代了递归来遍历整棵树。由于我们不需要回溯来找到 LCA 节点，所以完全可以不利用栈或者是递归的。实际上这个问题本身就是可以迭代的，我们只需要找到分割点就可以了。这个分割点就是能让节点 p 和节点 q 不能在同一颗子树上的那个节点，或者是节点 p 和节点 q 中的一个，这种情况下其中一个节点是另一个节点的父亲节点。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        int pVal = p.val;
        int qVal = q.val;

        TreeNode node = root;
        
        while (node != null) {
            int parentVal = node.val;
            if (pVal > parentVal && qVal > parentVal) {  
                node = node.right;
            } else if (pVal < parentVal && qVal < parentVal) {
                node = node.left;
            } else {
                return node;
            }
        }
        return null;
    }
}

时间复杂度：O(N)
其中 N 为 BST 中节点的个数，在最坏的情况下我们可能需要遍历 BST 中所有的节点。
空间复杂度：O(1)

3.二叉树的最近公共祖先（LeetCode - 236）

该题目和上一题LeetCode - 235的唯一区别是只给出了是二叉树，并不是二叉搜索树。

方法：递归。首先我们判断root根节点是否等于p或q，如果等于其中一个那么root节点就是LCA。没有找到的话接下来分别遍历左子树和右子树，看左子树和右子树中能否找到p或q。最后进行判断，如果遍历左子树的结果为空（也就是left== null），说明p和q都在右子树上，那么LCA就是右子树遍历的结果right。如果遍历右子树的结果为空（也就是right == null），说明p和q都在右子树上，那么LCA就是右子树遍历的结果left。如果遍历左右子树结果都不为空，说明p和q一个在左子树上一个在右子树上，那么要找的LCA就是root节点了

class Solution {
    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) ;
        return left == null ? right : right == null ? left : root;
    }
}

时间复杂度：O(N)

空间复杂度：O(N)