二叉树基础

一、二叉树深度优先遍历

只介绍先序遍历：

(1) 第一种方法是使用stack的结构

(2) 主要要理解后面的分治法

Version 0: Non-Recursion (Recommend)
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> preorder = new ArrayList<Integer>();
        
        if (root == null) {
            return preorder;
        }
        
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            preorder.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        
        return preorder;
    }
}

//Version 1: Traverse
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        traverse(root, result);
        return result;
    }
    // 把root为跟的preorder加入result里面
    private void traverse(TreeNode root, ArrayList<Integer> result) {
        if (root == null) {
            return;
        }

        result.add(root.val);
        traverse(root.left, result);
        traverse(root.right, result);
    }
}

//Version 2: Divide & Conquer
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // null or leaf
        if (root == null) {
            return result;
        }

        // Divide
        ArrayList<Integer> left = preorderTraversal(root.left);
        ArrayList<Integer> right = preorderTraversal(root.right);

        // Conquer
        result.add(root.val);
        result.addAll(left);
        result.addAll(right);
        return result;
    }
}

二、分治法

三个例子：

　　归并排序

　　快速排序

　　大多数的二叉树问题

归并排序和快速排队都是典型的分治法。

归并排序：强调先局部有序，再归并为整体有序. 最差时间复杂度和平均复杂度都是log(n)*n，但是有问题就是在归并的时候需要额外的空间，同时它还是一个稳定(什么是稳定，相同元素的位置是否需要移动)的排序算法。

快速排序：强调先整体有序，再partition为局部有序，最差情况是n*n，平均复杂度是log(n)*n，不需要额外空间，需要swap操作，是一个不稳定的排序算法。

数学归纳法是成立的，一切都是建立数学归纳法是成立以及空集存在的可能性上建立的。

二叉树问题:

(1) 最大深度:

　　depth(TreeNode) = max(depth(left), depth(right))+1

(2) 是否是平衡树?

是平衡树：

　　leftChild是平衡树

　　rightChild是平衡树

　　| depth(leftChild) - depth(rightChild) | <1

class ResultType {
    public boolean isBalanced;
    public int maxDepth;
    public ResultType(boolean isBalanced, int maxDepth) {
        this.isBalanced = isBalanced;
        this.maxDepth = maxDepth;
    }
}

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
        return helper(root).isBalanced;
    }
    
    private ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(true, 0);
        }
        
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        // subtree not balance
        if (!left.isBalanced || !right.isBalanced) {
            return new ResultType(false, -1);
        }
        
        // root not balance
        if (Math.abs(left.maxDepth - right.maxDepth) > 1) {
            return new ResultType(false, -1);
        }
        
        return new ResultType(true, Math.max(left.maxDepth, right.maxDepth) + 1);
    }
}

(3) 最近公共祖先问题

问题描述：给2个节点n1 n2 (n1,n2都存在)，寻找二者最近的公共祖先.

find(root, n1, n2)

分治法，从根出发，自顶向下，从左右2个子树上去寻找.

先考虑单子树的情况：

• 如果root是n1, n2一定存在的话，肯定在n1下面，直接返回root
• root是n2同理
• 如果root == null, 表明这个子树找不到了返回null

合并2个子树的寻找结果 leftResult和rightResult.

如果leftResult非空，表明至少出现一个或者出现2个.

同理，如果rightResult非空，表明至少出现一个或者出现2个.

因此:

如果都非空，表示一边一个，返回root

如果一边为空，另一边非空，返回非空的那个

如果都为空，没有找到? 和假设不合，不考虑

代码如下：

// 在root为根的二叉树中找A,B的LCA:
    // 如果找到了就返回这个LCA
    // 如果只碰到A，就返回A
    // 如果只碰到B，就返回B
    // 如果都没有，就返回null


    /**
     * 这里有个假设, node1和node2都必须存在. 假如不存在下面的方法是有问题的.
     *
     * @param root  以root为搜索基础节点
     * @param node1 要寻找的node1
     * @param node2 要寻找的node2
     * @return 二者的最近公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        if (root == null) {
            return null;
        }

        if (root == node1) {
            return node1;
        }

        if (root == node2) {
            return node2;
        }

        TreeNode leftResult = lowestCommonAncestor(root.left, node1, node2);
        TreeNode rightResult = lowestCommonAncestor(root.left, node1, node2);
        if (leftResult == null && rightResult == null) {
            return null;
        } else if (leftResult != null & rightResult != null) {
            return root;
        } else if (leftResult == null && rightResult != null) {
            return rightResult;
        } else {
            return leftResult;
        }
    }

 总结使用分治法解决的大致代码模板:

public class Solution {
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // do something with root
        traverse(root.left);
        // do something with root
        traverse(root.right);
        // do something with root
    }
}


Tempate 2: Divide & Conquer

public class Solution {
    public ResultType traversal(TreeNode root) {
        // null or leaf
        if (root == null) {
            // do something and return;
        }
        
        // Divide
        ResultType left = traversal(root.left);
        ResultType right = traversal(root.right);
        
        // Conquer
        ResultType result = Merge from left and right.
        return result;
    }
}

三、BFS基础

三种方式:

2个队列

1个队列 + Dummy Node

1个队列 (best)

 
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: buttom-up level order a list of lists of integer
     */
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode head = queue.poll();
                level.add(head.val);
                if (head.left != null) {
                    queue.offer(head.left);
                }
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            result.add(level);
        }
        
        Collections.reverse(result);
        return result;
    }
}

四、二叉搜索树

左子树比根节点小， 且右子树比根节点大.

(1) 判断是否是bst

(2) range query

(3) remove node

(4) Iterator