算法（三）-二叉树

一、概念

• 树：由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
• 二叉树：每个结点至多只有二棵子树。
• 满二叉树：叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点。
• 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除第d层外的所有节点构成满二叉树，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
• 二叉查找树(BST)：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树；
• 平衡二叉树(AVL)：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。

二、二叉树性质

• 在二叉树中，第i层的结点总数不超过2^(i-1)；
• 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点；
• 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2， 则N0=N2+1；
• 具有n个结点的完全二叉树的深度为int（log2n）+1

三、二叉树常见算法题

class TreeNode {
    TreeNode left;
    TreeNode right;
    int value;
    public TreeNode(int v) {
        value = v;
    }
}
public class test {
    /**
     * 构建完全二叉查找树 4 2 6 1 3 5 7
     */
    public static TreeNode getBinarySortTree() {
        TreeNode root = new TreeNode(4);
        TreeNode l = new TreeNode(2);
        TreeNode r = new TreeNode(6);
        TreeNode ll = new TreeNode(1);
        TreeNode lr = new TreeNode(3);
        TreeNode rl = new TreeNode(5);
        TreeNode rr = new TreeNode(7);
        root.left = l;
        root.right = r;
        l.left = ll;
        l.right = lr;
        r.left = rl;
        r.right = rr;
        return root;
    }
    /**
     * 随便构建一棵二叉树
     */
    public static TreeNode getBinaryTree() {
        TreeNode root = new TreeNode(4);
        TreeNode l = new TreeNode(2);
        TreeNode r = new TreeNode(6);
        TreeNode lr = new TreeNode(3);
        TreeNode rl = new TreeNode(5);
        TreeNode rr = new TreeNode(7);
        TreeNode lrl = new TreeNode(1);
        root.left = l;
        root.right = r;
        l.right = lr;
        r.left = rl;
        r.right = rr;
        lr.left = lrl;
        return root;
    }
    /**
     * 1 二叉树的遍历
     * 
     * @param args
     */
    // 前序遍历： 根左右
    //递归
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value);
        preOrder(root.left);
        preOrder(root.right);
    }
    //非递归
    public static void preOrder2(TreeNode head) {
        if (head == null) {
            return;
        }
        //几乎与层序遍历一样，除了队列换成堆栈
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            System.out.print(head.value + " ");
            if (head.right != null)
                stack.push(head.right);
            if (head.left != null)
                stack.push(head.left);
        }
    }

    // 中序遍历： 左根右
//递归
    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.value);
        inOrder(root.right);
    }
 //非递归
    public static void midOrder2(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                // 当前节点不为空, 将自己压进栈并将自己的左孩子作为当前节点（压入左边界）
                stack.push(head);
                head = head.left;
            } else {
                // 当前节点为空（没有左孩子了）, 将栈顶元素弹出作为当前节点, 并将当前节点的右孩子压进栈
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
    }


    // 后序遍历： 左右根
//递归
    public static void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value);
    }
  //非递归
    public static void postOrder2(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();//借助辅助存储实现 根右左，利用栈的特性输出左右根
        stack1.push(head);
        while (!stack1.isEmpty()) {
            head = stack1.pop();
            stack2.push(head);
            // 有左孩子就先压入左孩子
            if (head.left != null)
                stack1.push(head.left);
            // 有右孩子就后压入右孩子
            if (head.right != null)
                stack1.push(head.right);
        }
        // 逆序打印 根 右 左 的结果，就是后序遍历的结果
        while (!stack2.isEmpty())
            System.out.print(stack2.pop().value + " ");
    }

    // 层次遍历
    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 这里借助队列来实现
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.value);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    /**
     * 2 二叉树深度、叶子节点相关
     */
    // 求二叉树的深度
    public static int getTreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getTreeDepth(root.left);
        int right = getTreeDepth(root.right);
        // 返回max是最大深度，min是最小深度
        return Math.max(left, right) + 1;
    }
    // 深度为N的满二叉树，叶子结点数为：2^n-1
    public static int getLeafCount(int N) {
        return (int) Math.pow(2, N - 1);
    }
    // 3 反转二叉树/求二叉树的镜像
    public static void invertBanaryTree(TreeNode root) {
        if (root == null) {
            return;
        }
        invertBanaryTree(root.left);
        invertBanaryTree(root.right);
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
    }
    /**
     * 4 二叉搜索树转换成一个排序的双向链表
     */
    // 用于储存中序遍历当前的节点，作为中间变量，将双向指针链接起来
    static TreeNode cur = null;
    // 递归到最深层，返回双向链表的头
    static TreeNode head = null;
    public static TreeNode convertDoubleLinkedList(TreeNode root) {
        if (root == null) {
            return null;
        }
        convertDoubleLinkedList(root.left); // 左
        // 中序遍历在中间进行处理
        // left= 前驱， right=后继
        root.left = cur;
        if (cur != null) {
            cur.right = root;
        }
        // pre指向root
        cur = root;
        // 递归到最深处才将头赋值，也就是双向链表的头
        if (head == null) {
            head = root;
        }
        convertDoubleLinkedList(root.right); // 右
        return head;
    }
    // 5 二叉查找树的第k个结点(给定一棵二叉搜索树，请找出其中的第k小的结点)
    static int count = 0;
    public static TreeNode getKthNode(TreeNode root, int k) {
        if (root == null) {
            return null;
        }
        // 二叉搜索树按照中序遍历的顺序打印出来正好就是从小到大顺序排列，然后找到第k个结点就是结果。
        TreeNode left = getKthNode(root.left, k);
        if (left != null) {
            return left;
        }
        count++;
        if (count == k) {
            return root;
        }
        TreeNode right = getKthNode(root.right, k);
        if (right != null) {
            return right;
        }
        return null;
    }
    // 6 二叉树中和为某个值的路径
    public static void findPath(TreeNode root, int k) {
        if (root == null)
            return;
        Stack<Integer> stack = new Stack<Integer>();
        findPath(root, k, stack);
    }
    public static void findPath(TreeNode root, int k, Stack<Integer> path) {
        if (root == null)
            return;
        if (root.left == null && root.right == null) {
            if (root.value == k) {
                for (int i : path) {
                    System.out.print(i + ",");
                }
                // 还要加上当前等于K的value
                System.out.print(root.value);
            }
        } else {
            path.push(root.value);
            findPath(root.left, k - root.value, path);
            findPath(root.right, k - root.value, path);
            path.pop();
        }
    }
    public static void main(String[] args) {
        TreeNode root = getBinarySortTree();
        TreeNode linkedList = convertDoubleLinkedList(root);
        TreeNode tail = null;
        while (linkedList != null) {
            System.out.print(linkedList.value);
            tail = linkedList;
            linkedList = linkedList.right;
        }
        System.out.println("");
        while (tail != null) {
            System.out.print(tail.value);
            tail = tail.left;
        }
    }
}

简单写了几道高频率出现的二叉树算法题，用得比较多的算法思想还是递归，大部分用到的核心逻辑还是排序。