面试算法大全-树与二叉树总结

矫情吗；* 2022-10-17 13:50 141阅读 0赞

## 6、树结构 ##

### 6.1 树数据结构体系 ###

#### 6.1.1 二叉树和基本实现 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1OTY0NTU_size_16_color_FFFFFF_t_70_pic_center]

二叉树数据结构定义：

public class TreeNode {
        
        int val;
        TreeNode left;
        TreeNode right;
    
        public TreeNode() {
        
        }
    
        public TreeNode(int val) {
        
            this.val = val;
        }
    
        public TreeNode(int val, TreeNode left, TreeNode right) {
        
            this.val = val;
            this.left = left;
            this.right = right;
        }
    
        public int getVal() {
        
            return val;
        }
    
        public void setVal(int val) {
        
            this.val = val;
        }
    
        public TreeNode getLeft() {
        
            return left;
        }
    
        public void setLeft(TreeNode left) {
        
            this.left = left;
        }
    
        public TreeNode getRight() {
        
            return right;
        }
    
        public void setRight(TreeNode right) {
        
            this.right = right;
        }
    }

二叉树的前序，中序，后序，层序遍历(递归)

/**
         * 先序遍历
         *
         * @param node
         */
    public void preOrder(Node node) {
        
        if (node == null) {
        
            return;
        }
        System.out.print(node.val);
        preOrder(node.left);
        preOrder(node.right);
    }
    /**
         * 中序遍历
         *
         * @param node
         */
    public void midOrder(Node node) {
        
        if (node == null) {
        
            return;
        }
        midOrder(node.left);
        System.out.print(node.val);
        midOrder(node.right);
    }
    /**
         * 后序遍历
         *
         * @param node
         */
    public void postOrder(Node node) {
        
        if (node == null) {
        
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val);
    }

二叉树的前序，中序，后序，层序遍历(非递归)

/**
         * 前序遍历
         * 非递归形式
         *
         * @param root
         */
    private void preOrderStack(Node root) {
        
        if (root == null) {
        
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
        
            Node node = stack.pop();
            System.out.print(node.val);
            if (node.right != null) {
        
                stack.push(node.right);
            }
            if (node.left != null) {
        
                stack.push(node.left);
            }
        }
    }
    /**
         * 中序遍历，非递归形式
         *
         * @param root
         */
    private void midOrderStack(Node root) {
        
        if (root == null) {
        
            return;
        }
        Stack<Node> stack = new Stack<>();
        //找一个辅助节点，借助辅助节点寻找最左节点。
        Node cur = root;
        while (!stack.isEmpty() || cur != null) {
        
            while (cur != null) {
        
                stack.push(cur);
                cur = cur.left;
            }
            Node node = stack.pop();
            System.out.print(node.val);
            if (node.right != null) {
        
                cur = node.right;
            }
        }
    }
    /**
         * 后序遍历 ，非递归形式
         *
         * @param root
         */
    private void postOrderStack(Node root) {
        
        if (root == null) {
        
            return;
        }
        Stack<Node> stack = new Stack<>();
        Stack<Node> stack1 = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
        
            Node node = stack.pop();
            stack1.push(node);
            if (node.left != null) {
        
                stack.push(node.left);
            }
            if (node.right != null) {
        
                stack.push(node.right);
            }
        }
        while (!stack1.isEmpty()) {
        
            System.out.print(stack1.pop().val);
        }
    }

二叉树的层序遍历

/**
         * 层序遍历
         * @param root
         */
    private void bfs(Node root) {
        
        if (root == null) {
        
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
        
            Node node=queue.poll();
            System.out.print(node.val);
            if (node.left!=null){
        
                queue.offer(node.left);
            }
            if (node.right!=null){
        
                queue.offer(node.right);
            }
        }
    }
    /**
         * 层序遍历,保存每一层遍历的值
         * @param root
         */
    private List<List<String>> bfs2(Node root){
        
        List<List<String>> res=new ArrayList<>();
        if (root==null){
        
            return res;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        List<String> tmp;
        while (!queue.isEmpty()){
        
            int size = queue.size();
            tmp=new ArrayList<>();
            while (size-- >0){
        
                Node node=queue.poll();
                tmp.add(node.val);
                if (node.left!=null){
        
                    queue.add(node.left);
                }
                if (node.right!=null){
        
                    queue.add(node.right);
                }
            }
            res.add(tmp);
        }
        return  res;
    }

二叉搜索树具有有以下性质的二叉树：  
  （1）若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。  
  （2）若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。  
  （3）左、右子树也分别为二叉搜索树。

/**
     * Java实现二叉查找树
     * @author Kiritor
     * @param <T>*/
    public class BinarySearchTree<T extends Comparable<? super T>> {
        
        /**结点数据结构*/
        static class BinaryNode<T>
        {
        
            T data;
            BinaryNode<T> left;
            BinaryNode<T> right;
            public BinaryNode(T data) {
        
                this(data,null,null);
            }
            public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
        
                this.data =data;
                this.left = left;
                this.right =right;
            }
            public BinaryNode()
            {
        
                data =null;
                this.left = left;
                this.right =right;
            }
        }
        private BinaryNode<T> rootTree;
        /**构造一颗空的二叉查找树*/
        public BinarySearchTree()
        {
        
            rootTree = null;
        }
        /**清空二叉查找树*/
        public void clear()
        {
        
            rootTree = null;
        }
        /**判断是否为空*/
        public boolean isEmpty()
        {
        
            return rootTree == null;
        }
        /**查找指定的元素,默认从
         * 根结点出开始查询*/
        public boolean contains(T t)
        {
        
            return contains(t, rootTree);
    
        }
        /**找到二叉查找树中的最小值*/
        public T findMin()
        {
        
            if(isEmpty())
            {
        
                System.out.println("二叉树为空");
                return null;
            }else {
        
                return findMin(rootTree).data;
            }
    
        }
        /**找到二叉查找树中的最大值*/
        public T findMax()
        {
        
            if(isEmpty())
            {
        
                System.out.println("二叉树为空");
                return null;
            }else {
        
                return findMax(rootTree).data;
            }
        }
        /**插入元素*/
        public void insert(T t)
        {
        
            rootTree = insert(t, rootTree);
        }
        /**删除元素*/
        public void remove(T t)
        {
        
            rootTree = remove(t,rootTree);
        }
        /**打印二叉查找树*/
        public void printTree()
        {
        
    
        }
        /**从某个结点出开始查找元素*/
        public boolean contains(T t, BinaryNode<T> node)
        {
        
            if(node==null) {
        
                return false;
            }
            int result = t.compareTo(node.data);
            if(result>0) {
        
                return contains(t,node.right);
            } else if(result<0) {
        
                return contains(t, node.left);
            } else {
        
                return true;
            }
        }
        /**查询出最小元素所在的结点*/
        public BinaryNode<T> findMin(BinaryNode<T> node)
        {
        
            if(node==null) {
        
                return null;
            } else if(node.left==null) {
        
                return node;
            }
            return findMin(node.left);//递归查找
        }
        /**查询出最大元素所在的结点*/
        public BinaryNode<T> findMax(BinaryNode<T> node)
        {
        
            if(node!=null)
            {
        
                while(node.right!=null) {
        
                    node=node.right;
                }
            }
            return node;
        }
        /**在某个位置开始判断插入元素*/
        public BinaryNode<T> insert(T t,BinaryNode<T> node)
        {
        
            if(node==null)
            {
        
                //新构造一个二叉查找树
                return new BinaryNode<T>(t, null, null);
            }
            int result = t.compareTo(node.data);
            if(result<0) {
        
                node.left= insert(t,node.left);
            } else if(result>0) {
        
                node.right= insert(t,node.right);
            } else {
        
                ;//doNothing
            }
            return node;
        }
        /**在某个位置开始判断删除某个结点*/
        public BinaryNode<T> remove(T t,BinaryNode<T> node)
        {
        
            if(node == null) {
        
                return node;//没有找到,doNothing
            }
            int result = t.compareTo(node.data);
            if(result>0) {
        
                node.right = remove(t,node.right);
            } else if(result<0) {
        
                node.left = remove(t,node.left);
            } else if(node.left!=null&&node.right!=null)
            {
        
                node.data = findMin(node.right).data;
                node.right = remove(node.data,node.right);
            }
            else {
        
                node = (node.left!=null)?node.left:node.right;
            }
            return node;
    
        }
        public BinaryNode<Integer> init()
        {
        
            BinaryNode<Integer> node3 = new BinaryNode<Integer>(3);
            BinaryNode<Integer> node1 = new BinaryNode<Integer>(1);
            BinaryNode<Integer> node4 = new BinaryNode<Integer>(4,node3,null);
            BinaryNode<Integer> node2 = new BinaryNode<Integer>(2,node1,node4);
            BinaryNode<Integer> node8 = new BinaryNode<Integer>(8);
            BinaryNode<Integer> root = new BinaryNode<Integer>(6,node2,node8);
            return root;
        }
        public void preOrder(BinaryNode node) {
        
            if (node != null) {
        
                System.out.print(node.data);
                preOrder(node.left);
                preOrder(node.right);
            }
        }
        /*简单测试*/
        public static void main(String[] args) {
        
            BinarySearchTree  searchTree = new BinarySearchTree<>();
            BinaryNode<Integer> node= searchTree.init();
            searchTree.rootTree=node;
            searchTree.preOrder(searchTree.rootTree);
            searchTree.remove(4);
            searchTree.preOrder(searchTree.rootTree);
        }
    }

平衡二叉树

（1）它的结点左子树和右子树的深度之差不超过1

（2）该结点的左子树和右子树都是一棵平衡二叉树

/**
     *二叉平衡树简单实现
     *@author kiritor
     */
    public class AvlTree< T extends Comparable< ? super T>>
    {
        
        private static class AvlNode< T>{
        //avl树节点
    
            AvlNode( T theElement )
            {
        
                this( theElement, null, null );
            }
            AvlNode( T theElement, AvlNode< T> lt, AvlNode< T> rt )
            {
        
                element  = theElement;
                left     = lt;
                right    = rt;
                height   = 0;
            }
            T           element;      // 节点中的数据
            AvlNode< T>  left;         // 左儿子
            AvlNode< T>  right;        // 右儿子
            int         height;       // 节点的高度
        }
        private AvlNode< T> root;//avl树根
        public AvlTree( )
        {
        
            root = null;
        }
        //在avl树中插入数据，重复数据复略
        public void insert( T x )
        {
        
            root = insert( x, root );
        }
        //在avl中删除数据,这里并未实现
        public void remove( T x )
        {
        
            System.out.println( "Sorry, remove unimplemented" );
        }
        //在avl树中找最小的数据
        public T findMin( )
        {
        
            if( isEmpty( ) ) {
        
                System.out.println("树空");
            }
            ;
            return findMin( root ).element;
        }
        //在avl树中找最大的数据
        public T findMax( )
        {
        
            if( isEmpty( ) ) {
        
                System.out.println("树空");
            }
            return findMax( root ).element;
        }
        //搜索
        public boolean contains( T x )
        {
        
            return contains( x, root );
        }
        public void makeEmpty( )
        {
        
            root = null;
        }
        public boolean isEmpty( )
        {
        
            return root == null;
        }
        //排序输出avl树
        public void printTree( )
        {
        
            if( isEmpty( ) ) {
        
                System.out.println( "Empty tree" );
            } else {
        
                printTree( root );
            }
        }
        private AvlNode< T> insert( T x, AvlNode< T> t )
        {
        
            if( t == null ) {
        
                return new AvlNode< T>( x, null, null );
            }
            int compareResult = x.compareTo( t.element );
            if( compareResult < 0 )
            {
        
                t.left = insert( x, t.left );//将x插入左子树中
                if( height( t.left ) - height( t.right ) == 2 )//打破平衡
                {
        
                    if( x.compareTo( t.left.element ) < 0 )//LL型（左左型）
                    {
        
                        t = rotateWithLeftChild( t );
                    } else   //LR型（左右型）
                    {
        
                        t = doubleWithLeftChild( t );
                    }
                }
            }
            else if( compareResult > 0 )
            {
        
                t.right = insert( x, t.right );//将x插入右子树中
                if( height( t.right ) - height( t.left ) == 2 )//打破平衡
                {
        
                    if( x.compareTo( t.right.element ) > 0 )//RR型（右右型）
                    {
        
                        t = rotateWithRightChild( t );
                    } else                           //RL型
                    {
        
                        t = doubleWithRightChild( t );
                    }
                }
            }
            else {
        
                ;  // 重复数据，什么也不做
            }
            t.height = Math.max( height( t.left ), height( t.right ) ) + 1;//更新高度
            return t;
        }
        //找最小
        private AvlNode< T> findMin( AvlNode< T> t )
        {
        
            if( t == null ) {
        
                return t;
            }
            while( t.left != null ) {
        
                t = t.left;
            }
            return t;
        }
        //找最大
        private AvlNode< T> findMax( AvlNode< T> t )
        {
        
            if( t == null ) {
        
                return t;
            }
            while( t.right != null ) {
        
                t = t.right;
            }
            return t;
        }
        //搜索（查找）
        private boolean contains( T x, AvlNode t )
        {
        
            while( t != null )
            {
        
                int compareResult = x.compareTo( (T) t.element );
                if( compareResult < 0 ) {
        
                    t = t.left;
                } else if( compareResult > 0 ) {
        
                    t = t.right;
                } else {
        
                    return true;    // Match
                }
            }
            return false;   // No match
        }
        //中序遍历avl树
        private void printTree( AvlNode< T> t )
        {
        
            if( t != null )
            {
        
                printTree( t.left );
                System.out.println( t.element );
                printTree( t.right );
            }
        }
        //求高度 
        private int height( AvlNode< T> t )
        {
        
            return t == null ? -1 : t.height;
        }
        //带左子树旋转,适用于LL型
        private AvlNode< T> rotateWithLeftChild( AvlNode< T> k2 )
        {
        
            AvlNode< T> k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;
            k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
            k1.height = Math.max( height( k1.left ), k2.height ) + 1;
            return k1;
        }
        //带右子树旋转，适用于RR型
        private AvlNode< T> rotateWithRightChild( AvlNode< T> k1 )
        {
        
            AvlNode< T> k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
            k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
            k2.height = Math.max( height( k2.right ), k1.height ) + 1;
            return k2;
        }
        //双旋转，适用于LR型
        private AvlNode< T> doubleWithLeftChild( AvlNode< T> k3 )
        {
        
            k3.left = rotateWithRightChild( k3.left );
            return rotateWithLeftChild( k3 );
        }
        //双旋转,适用于RL型
        private AvlNode< T> doubleWithRightChild( AvlNode< T> k1 )
        {
        
            k1.right = rotateWithLeftChild( k1.right );
            return rotateWithRightChild( k1 );
        }
        // Test program
        public static void main( String [ ] args )
        {
        
            AvlTree< Integer> t = new AvlTree< Integer>( );
            final int NUMS = 200;
            final int GAP  =   17;
            System.out.println( "Checking... (no more output means success)" );
            for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) {
        
                t.insert( i );
            }
            t.printTree( );
            System.out.println(t.height(t.root));
        }
    }

完全二叉树

（1）若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，

（2）第k 层所有的结点都连续集中在最左边，这就是完全二叉树。

满二叉树

一棵二叉树的结点要么是叶子结点，要么它有两个子结点

如果一个二叉树的层数为K，且结点总数是(2^k) -1，则它就是满二叉树

#### 6.1.2 堆（来自数组的树） ####

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RCV7Ia6u-1622708209520)(C:\\Users\\HuFeiHu\\AppData\\Roaming\\Typora\\typora-user-images\\image-20201113132216833.png)\]

堆的性质，堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：  
1.堆中某个节点的值总是不大于或不小于其父节点的值。  
2.堆总是一棵完全二叉树。

public class Heap {
        
        private int[] arr;       // 堆是完全二叉树，底层用数组存储
        private int capacity;    // 堆中能存储的最大元素数量
        private int n;          // 当前堆中元素数量
        public Heap(int count) {
        
            capacity = count;
            arr = new int[capacity+1];
            n = 0;
        }
        public void insert(int value) {
        
            if (n >= capacity) {
        
                // 超过堆大小了，不能再插入元素
                return;
            }
            n++;
            // 先将元素插入到队尾中
            arr[n] = value;
    
            int i = n;
            // 由于我们构建的是一个大顶堆，所以需要不断调整以让其满足大顶堆的条件
            while (i/2 > 0 && arr[i] > arr[i/2]) {
        
                swap(arr, i, i/2);
                i = i / 2;
            }
        }
        /**
         * 移除堆顶元素
         */
        public void removeTopElement() {
        
            if (n == 0) {
        
                // 堆中如果没有元素，也就是不存在移除堆顶元素的情况了
                return;
            }
            int count = n;
            arr[1] = arr[count];
            --count;
            heapify(1, count);
        }
        /**
         * 自上而下堆化以满足大顶堆的条件
         */
        public void heapify(int index, int n) {
        
    
            while (true) {
        
                int maxValueIndex = index;
                if (2 * index <= n && arr[index] < arr[2 * index]) {
        
                    // 左节点比其父节点大
                    maxValueIndex = 2 * index;
                }
    
                if (2 * index + 1 <= n && arr[maxValueIndex] < arr[2 * index + 1]) {
        
                    // 右节点比左节点或父节点大
                    maxValueIndex = 2 * index + 1;
                }
    
                if (maxValueIndex == index) {
        
                    // 说明当前节点值为最大值，无需再往下迭代了
                    break;
                }
                swap(arr, index, maxValueIndex);
                index = maxValueIndex;
            }
        }
        /**
         * 交换数组第 i 和第 j 个元素
         */
        public static void swap(int[] arr, int i, int j)
        {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

第二种方法

import java.util.Arrays;
    
    class Heap {
        
        private final static int N = 100; //default size
        private int[] nums;
        private int size;
    
        public Heap(int[] nums) {
        
            this.nums = nums;
            this.size = nums.length;
            heapify(this.nums);
        }
        public Heap() {
        
            this.nums = new int[N];
        }
        /**
         * heapify an array, O(n)
         * @param nums An array to be heapified.
         */
        private void heapify(int[] nums) {
        
            for (int j = (size - 1) >> 1; j >= 0; j--) {
        
                siftDown(j);
            }
        }
        /**
         * append x to heap
         * O(logn)
         * @param x
         * <a href='http://www.jobbole.com/members/wx1409399284'>@return</a>
         */
        public int insert(int x) {
        
            if (size >= this.nums.length) {
        
                expandSpace();
            }
            size += 1;
            nums[size-1] = x;
            siftUp(size-1);
            return x;
        }
        /**
         * delete an element located in i position.
         * O(logn)
         * @param i
         * <a ref='http://www.jobbole.com/members/wx1409399284'>@return</a>
         */
        public int delete(int i) {
        
            rangeCheck(i);
            int key = nums[i];
    //将last元素覆盖过来,先siftDown; 再视情况考虑是否siftUp;
            int last = nums[i] = nums[size-1];
            size--;
            siftDown(i);
    //check #i的node的键值是否确实发生改变,若发生改变，则ok,否则为确保堆性质，则需要siftUp;
            if (i < size && nums[i] == last) {
        
                siftUp(i);
            }
            return key;
        }
        /**
         * remove the root of heap, return it's value, and adjust heap to maintain the heap's property.
         * O(logn)
         * <a href='http://www.jobbole.com/members/wx1409399284'>@return</a>
         */
        public int extractMin() {
        
            rangeCheck(0);
            int key = nums[0], last = nums[size-1];
            nums[0] = last;
            size--;
            siftDown(0);
            return key;
        }
        /**
         * return an element's index, if not exists, return -1;
         * O(n)
         * @param x
         * <a href='http://www.jobbole.com/members/wx1409399284'>@return</a>
         */
        public int search(int x) {
        
            for (int i = 0; i < size; i++) {
        
                if (nums[i] == x) {
        
                    return i;
                }
            }
            return -1;
        }
        /**
         * return but does not remove the root of heap.
         * O(1)
         * <a href='http://www.jobbole.com/members/wx1409399284'>@return</a>
         */
        public int peek() {
        
            rangeCheck(0);
            return nums[0];
        }
        private void siftUp(int i) {
        
            int key = nums[i];
            for (; i > 0;) {
        
                int p = (i - 1) >>> 1;
                if (nums[p] <= key) {
        
                    break;
                }
                nums[i] = nums[p];
                i = p;
            }
            nums[i] = key;
        }
        private void siftDown(int i) {
        
            int key = nums[i];
            for (;i < size / 2;) {
        
                int child = (i << 1) + 1;
                if (child + 1 < size && nums[child] > nums[child+1]) {
        
                    child++;
                }
                if (key <= nums[child]) {
        
                    break;
                }
                nums[i] = nums[child];
                i = child;
            }
            nums[i] = key;
        }
        private void rangeCheck(int i) {
        
            if (!(0 <= i && i < size)) {
        
                throw new RuntimeException("Index is out of boundary");
            }
        }
        private void expandSpace() {
        
            this.nums = Arrays.copyOf(this.nums, size * 2);
        }
        @Override
        public String toString() {
        
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int i = 0; i < size; i++) {
        
                sb.append(String.format((i != 0 ? ", " : "") + "%d", nums[i]));
            }
            sb.append("] ");
            return sb.toString();
        }
    }

堆的应用：海量实数中（一亿级别以上）找到TopK（一万级别以下）的数集合

import java.io.File;
    import java.io.FileNotFoundException;
    import java.io.PrintWriter;
    import java.io.UnsupportedEncodingException;
    import java.util.Arrays;
    import java.util.Scanner;
    import java.util.Set;
    import java.util.TreeSet;
    public class TopKNumbersInMassiveNumbersDemo {
        
        public static void main(String[] args) {
        
    // TODO Auto-generated method stub
            int[] topK = new int[]{
        50001,50002,50003,50004,50005};
            genData(1000 * 1000 * 1000, 500, topK);
            long t = System.currentTimeMillis();
            findTopK(topK.length);
            System.out.println(String.format("cost:%fs", (System.currentTimeMillis() - t) * 1.0 / 1000));
        }
        public static void genData(int N, int maxRandomNumer, int[] topK) {
        
            File f = new File("data.txt");
            int k = topK.length;
            Set<Integer> index = new TreeSet<>();
            for (;;) {
        
                index.add((int)(Math.random() * N));
                if (index.size() == k) {
        
                    break;
                }
            }
            System.out.println(index);
            int j = 0;
            try {
        
                PrintWriter pW = new PrintWriter(f, "UTF-8");
                for (int i = 0; i < N; i++) {
        
                    if(!index.contains(i)) {
        
                        pW.println((int)(Math.random() * maxRandomNumer));
                    } else {
        
                        pW.println(topK[j++]);
                    }
                }
                pW.flush();
            } catch (FileNotFoundException e) {
        
                e.printStackTrace();
            } catch (UnsupportedEncodingException e) {
        
                e.printStackTrace();
            }
        }
        public static void findTopK(int k) {
        
            int[] nums = new int[k];
            File f = new File("data.txt");
            try {
        
                Scanner scanner = new Scanner(f);
                for (int j = 0;j < k; j++) {
        
                    nums[j] = scanner.nextInt();
                }
                heapify(nums);
                //core
                while (scanner.hasNextInt()) {
        
                    int a = scanner.nextInt();
                    if (a <= nums[0]) {
        
                        continue;
                    } else {
        
                        nums[0] = a;
                        siftDown(0, k, nums);
                    }
    
                }
                System.out.println(Arrays.toString(nums));
            } catch (FileNotFoundException e) {
        
                e.printStackTrace();
            }
        }
        //O(n), minimal heap
        public static void heapify(int[] nums) {
        
            int size = nums.length;
            for (int j = (size - 1) >> 1; j >= 0; j--) {
        
                siftDown(j, size, nums);
            }
        }
        private static void siftDown(int i, int n, int[] nums) {
        
            int key = nums[i];
            for (;i < (n >>> 1);) {
        
                int child = (i << 1) + 1;
                if (child + 1 < n && nums[child] > nums[child+1]) {
        
                    child++;
                }
                if (key <= nums[child]) {
        
                    break;
                }
                nums[i] = nums[child];
                i = child;
            }
            nums[i] = key;
        }
    }

实现优先队列

第一种：

import java.util.Arrays;
    
    public class PriorityQueue2 {
        
        int[] arr = new int[10];
        int size;
        //交换
        public void swap(int[] arr, int i, int j) {
        
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        //向上调整
        public void shiftUp(int[] arr, int sz, int child) {
        
            int parent = (child - 1) / 2;
            while (child > 0) {
        
                if (arr[child] < arr[parent]) {
        
                    swap(arr, child, parent);
                    child = parent;
                    parent = (child - 1) / 2;
                } else {
        
                    break;
                }
            }
        }
        //向下调整
        public void shiftDown(int[] arr, int sz, int parent) {
        
            int child = 2 * parent + 1;
            while (child < sz) {
        
                if (child + 1 < sz && arr[child + 1] < arr[child]) {
        
                    child++;
                }
                if (arr[child] < arr[parent]) {
        
                    swap(arr, child, parent);
                    parent = child;
                    child = 2 * parent + 1;
                } else {
        
                    break;
                }
            }
        }
        //入队
        public void offer(int value) {
        
            if (size == arr.length) {
        
                arr = Arrays.copyOf(arr, arr.length * 2);
            }
            arr[size++] = value;    //尾插
            shiftUp(arr, size, size - 1);   //向上调整
        }
        //出队
        public int poll() {
        
            if (size > 0) {
        
                int peek = arr[0];
                swap(arr, 0, size - 1);
                size--;
                shiftDown(arr, size, 0);
                return peek;
            }
            return -1;
        }
        //取队顶元素
        public int peek() {
        
            return arr[0];
        }
        //判断是否为空
        public boolean isEmpty() {
        
            return size == 0;
        }
    }

第二种：

public class PriorityQueue {
        
        private int[] data;
        private int size;
    
        public PriorityQueue(int size){
        
            data = new int[size];
            this.size = 0;
        }
    
        public void push(int toInsert) throws Exception{
        
            if(size == data.length) {
        
                throw new Exception("Queue is full!");
            }
            if(size == 0){
        
                data[0] = toInsert;
            }else{
        
                int i = size -1;
                for( ; i >= 0 ; i--){
        
                    if(data[i] < toInsert){
        
                        data[i+1] = data[i];
                    }else{
        
                        break;
                    }
                }
                data[i+1] = toInsert;
            }
            size++;
        }
    
        public int pop() throws Exception{
        
            if(this.size == 0) {
        
                throw new Exception("Queue is empty!");
            }
            return data[--size];
        }
    
        public int peek() throws Exception{
        
            if(this.size == 0) {
        
                throw new Exception("Queue is empty!");
            }
            return data[size-1];
        }
    
        public int size(){
        
            return this.size;
        }
    
        public boolean isEmpty(){
        
            return (size == 0);
        }
    
        public boolean isFull(){
        
            return (size == data.length);
        }
    }

#### 6.1.3 红黑树 ####

性质1：每个节点要么是黑色，要么是红色。

性质2：根节点是黑色。

性质3：每个叶子节点（NIL）是黑色。

性质4：每个红色节点的两个子节点一定都是黑色。 不能有两个红色节点相连。

性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。

从性质5又可以推出：

性质5.1：如果一个节点存在黑子节点，那么该结点肯定有两个子节点。不然走另一条路就会少一层黑色结点。

#### 6.1.4 字典树（Trie） ####

实现

import java.util.Map;
    import java.util.TreeMap;
    
    public class Trie {
        
        private Node root;
        private int size;
        private static class Node {
        
            public boolean isWord;
            public Map<Character, Node> next;
            public Node() {
        
                next = new TreeMap<>();
            }
            public Node(boolean isWord) {
        
                this();
                this.isWord = isWord;
            }
        }
        public Trie() {
        
            root = new Node();
        }
        public int size() {
        
            return size;
        }
        public boolean isEmpty() {
        
            return size == 0;
        }
        /**
         * 插入操作
         *
         * @param word 单词
         */
        public void add(String word) {
        
            Node current = root;
            char[] cs = word.toCharArray();
            for (char c : cs) {
        
                Node next = current.next.get(c);
                if (next == null) {
        
                    current.next.put(c, new Node());
                }
                current = current.next.get(c);
            }
            //如果当前的node已经是一个word，则不需要添加
            if (!current.isWord) {
        
                size++;
                current.isWord = true;
            }
        }
        /**
         * 是否包含某个单词
         *
         * @param word 单词
         * @return 存在返回true，反之false
         */
        public boolean contains(String word) {
        
            Node current = root;
            for (int i = 0; i < word.length(); i++) {
        
                char c = word.charAt(i);
                Node node = current.next.get(c);
                if (node == null) {
        
                    return false;
                }
                current = node;
            }
            //如果只存在 panda这个词，查询 pan，虽然有这3个字母，但是并不存在该单词
            return current.isWord;
        }
        /**
         * Trie是否包含某个前缀
         *
         * @param prefix 前缀
         * @return
         */
        public boolean containsPrefix(String prefix) {
        
            Node current = root;
            for (int i = 0; i < prefix.length(); i++) {
        
                char c = prefix.charAt(i);
                Node node = current.next.get(c);
                if (node == null) {
        
                    return false;
                }
                current = node;
            }
            return true;
        }
    
        /*
         * 1，如果单词是另一个单词的前缀，只需要把该word的最后一个节点的isWord的改成false
         * 2，如果单词的所有字母的都没有多个分支，删除整个单词
         * 3，如果单词的除了最后一个字母，其他的字母有多个分支，
         */
        /**
         * 删除操作
         *
         * @param word
         * @return
         */
        public boolean remove(String word) {
        
            Node multiChildNode = null;
            int multiChildNodeIndex = -1;
            Node current = root;
            for (int i = 0; i < word.length(); i++) {
        
                Node child = current.next.get(word.charAt(i));
                //如果Trie中没有这个单词
                if (child == null) {
        
                    return false;
                }
                //当前节点的子节点大于1个
                if (child.next.size() > 1) {
        
                    multiChildNodeIndex = i;
                    multiChildNode = child;
                }
                current = child;
            }
            //如果单词后面还有子节点
            if (current.next.size() > 0) {
        
                if (current.isWord) {
        
                    current.isWord = false;
                    size--;
                    return true;
                }
                //不存在该单词，该单词只是前缀
                return false;
            }
            //如果单词的所有字母的都没有多个分支，删除整个单词
            if (multiChildNodeIndex == -1) {
        
                root.next.remove(word.charAt(0));
                size--;
                return true;
            }
            //如果单词的除了最后一个字母，其他的字母有分支
            if (multiChildNodeIndex != word.length() - 1) {
        
                multiChildNode.next.remove(word.charAt(multiChildNodeIndex + 1));
                size--;
                return true;
            }
            return false;
        }
    }

### 6.2 经典例题源码 ###

#### [二叉树的最大深度][Link 1] ####

方法一：递归

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            } else {
        
                int leftHeight = maxDepth(root.left);
                int rightHeight = maxDepth(root.right);
                return Math.max(leftHeight, rightHeight) + 1;
            }
        }
    }

方法二：广度优先搜索

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            int ans = 0;
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                while (size > 0) {
        
                    TreeNode node = queue.poll();
                    if (node.left != null) {
        
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
        
                        queue.offer(node.right);
                    }
                    size--;
                }
                ans++;
            }
            return ans;
        }
    }

#### [二叉树的最小深度][Link 2] ####

方法一：深度优先搜索

class Solution {
        
        public int minDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
    
            if (root.left == null && root.right == null) {
        
                return 1;
            }
    
            int min_depth = Integer.MAX_VALUE;
            if (root.left != null) {
        
                min_depth = Math.min(minDepth(root.left), min_depth);
            }
            if (root.right != null) {
        
                min_depth = Math.min(minDepth(root.right), min_depth);
            }
    
            return min_depth + 1;
        }
    }

方法二：广度优先搜索

class Solution {
        
        class QueueNode {
        
            TreeNode node;
            int depth;
    
            public QueueNode(TreeNode node, int depth) {
        
                this.node = node;
                this.depth = depth;
            }
        }
    
        public int minDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
    
            Queue<QueueNode> queue = new LinkedList<QueueNode>();
            queue.offer(new QueueNode(root, 1));
            while (!queue.isEmpty()) {
        
                QueueNode nodeDepth = queue.poll();
                TreeNode node = nodeDepth.node;
                int depth = nodeDepth.depth;
                if (node.left == null && node.right == null) {
        
                    return depth;
                }
                if (node.left != null) {
        
                    queue.offer(new QueueNode(node.left, depth + 1));
                }
                if (node.right != null) {
        
                    queue.offer(new QueueNode(node.right, depth + 1));
                }
            }
    
            return 0;
        }
    }

#### [平衡二叉树][Link 3] ####

一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1 。

方法一：自顶向下的递归

class Solution {
        
        public boolean isBalanced(TreeNode root) {
        
            if (root == null) {
        
                return true;
            } else {
        
                return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
            }
        }
    
        public int height(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            } else {
        
                return Math.max(height(root.left), height(root.right)) + 1;
            }
        }
    }

方法二：自底向上的递归

class Solution {
        
        public boolean isBalanced(TreeNode root) {
        
            return height(root) >= 0;
        }
    
        public int height(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int leftHeight = height(root.left);
            int rightHeight = height(root.right);
            if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
        
                return -1;
            } else {
        
                return Math.max(leftHeight, rightHeight) + 1;
            }
        }
    }

#### [特定深度节点链表][Link 4] ####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode[] listOfDepth(TreeNode tree) {
        
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(tree);
    
            List<ListNode> res = new ArrayList<>();
            ListNode dummy = new ListNode(0);
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                ListNode curr = dummy;
                for (int i = 0; i < size; i++) {
        
                    TreeNode treeNode = queue.poll();
                    curr.next = new ListNode(treeNode.val);
                    if (treeNode.left != null) {
        
                        queue.offer(treeNode.left);
                    }
                    if (treeNode.right != null) {
        
                        queue.offer(treeNode.right);
                    }
                    curr = curr.next;
                }
                res.add(dummy.next);
                dummy.next = null;
            }
    
            return res.toArray(new ListNode[] {
        });
        }
    }

#### [翻转二叉树][Link 5] ####

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if (root == null) {
        
                return null;
            }
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }
    }

#### [二叉树的最近公共祖先][Link 6] ####

方法一：非递归

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            //记录遍历到的每个节点的父节点。
            Map<TreeNode, TreeNode> parent = new HashMap<>();
            Queue<TreeNode> queue = new LinkedList<>();
            parent.put(root, null);//根节点没有父节点，所以为空
            queue.add(root);
            //直到两个节点都找到为止。
            while (!parent.containsKey(p) || !parent.containsKey(q)) {
        
                //队列是一边进一边出，这里poll方法是出队，
                TreeNode node = queue.poll();
                if (node.left != null) {
        
                    //左子节点不为空，记录下他的父节点
                    parent.put(node.left, node);
                    //左子节点不为空，把它加入到队列中
                    queue.add(node.left);
                }
                //右节点同上
                if (node.right != null) {
        
                    parent.put(node.right, node);
                    queue.add(node.right);
                }
            }
            Set<TreeNode> ancestors = new HashSet<>();
            //记录下p和他的祖先节点，从p节点开始一直到根节点。
            while (p != null) {
        
                ancestors.add(p);
                p = parent.get(p);
            }
            //查看p和他的祖先节点是否包含q节点，如果不包含再看是否包含q的父节点……
            while (!ancestors.contains(q))
                q = parent.get(q);
            return q;
        }

方法二：递归写法

public TreeNode lowestCommonAncestor(TreeNode cur, TreeNode p, TreeNode q) {
        
            if (cur == null || cur == p || cur == q)
                return cur;
            TreeNode left = lowestCommonAncestor(cur.left, p, q);
            TreeNode right = lowestCommonAncestor(cur.right, p, q);
            //如果left为空，说明这两个节点在cur结点的右子树上，我们只需要返回右子树查找的结果即可
            if (left == null)
                return right;
            //同上
            if (right == null)
                return left;
            //如果left和right都不为空，说明这两个节点一个在cur的左子树上一个在cur的右子树上，
            //我们只需要返回cur结点即可。
            return cur;
        }

#### [二叉搜索树的最近公共祖先][Link 7] ####

方法一：递归

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if(root.val < p.val && root.val < q.val)
                return lowestCommonAncestor(root.right, p, q);
            if(root.val > p.val && root.val > q.val)
                return lowestCommonAncestor(root.left, p, q);
            return root;
        }
    }

方法二：迭代

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            while(root != null) {
        
                if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                    root = root.right; // 遍历至右子节点
                else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                    root = root.left; // 遍历至左子节点
                else break;
            }
            return root;
        }
    }
    // 优化：若可保证 p.val < q.valp.val<q.val ，则在循环中可减少判断条件。
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if(p.val > q.val) {
         // 保证 p.val < q.val
                TreeNode tmp = p;
                p = q;
                q = tmp;
            }
            while(root != null) {
        
                if(root.val < p.val) // p,q 都在 root 的右子树中
                    root = root.right; // 遍历至右子节点
                else if(root.val > q.val) // p,q 都在 root 的左子树中
                    root = root.left; // 遍历至左子节点
                else break;
            }
            return root;
        }
    }

#### [对称二叉树][Link 8] ####

方法一：递归

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            return check(root, root);
        }
        public boolean check(TreeNode p, TreeNode q) {
        
            if (p == null && q == null) {
        
                return true;
            }
            if (p == null || q == null) {
        
                return false;
            }
            return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
        }
    }

方法二：迭代

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            return check(root, root);
        }
        public boolean check(TreeNode u, TreeNode v) {
        
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(u);
            q.offer(v);
            while (!q.isEmpty()) {
        
                u = q.poll();
                v = q.poll();
                if (u == null && v == null) {
        
                    continue;
                }
                if ((u == null || v == null) || (u.val != v.val)) {
        
                    return false;
                }
                q.offer(u.left);
                q.offer(v.right);
                q.offer(u.right);
                q.offer(v.left);
            }
            return true;
        }
    }

#### 上下反转二叉树 ####

class Solution {
        
        // 处理之后的根节点
         TreeNode head;
        public  TreeNode upsideDownBinaryTree(TreeNode root) {
        
            if (root == null) {
        
                return null;
            }
            dfs(root);  // 对 root 进行上下翻转
            return head;
        }
        public  TreeNode dfs(TreeNode node) {
        
            if (node == null) {
        
                return null;
            }
            if (node.left == null && node.right == null) {
        
                if (head == null) {
        
                    // 最左边的节点即为实际的根节点
                    head = node;
                }
                return node;
            }
            TreeNode left = dfs(node.left);
            TreeNode right = dfs(node.right);
            if (left != null) {
        
                // 左孩子的左子树为当前的右节点
                left.left = right;
                // 左孩子的右子树为当前父节点
                left.right = node;
            }
            // 清空的当前父节点的左右子树
            node.right = null;
            node.left = null;
            return node;
        }
    }

#### [二叉搜索树中的众数][Link 9] ####

中序遍历

class Solution {
        
        List<Integer> answer = new ArrayList<Integer>();
        int base, count, maxCount;
    
        public int[] findMode(TreeNode root) {
        
            dfs(root);
            int[] mode = new int[answer.size()];
            for (int i = 0; i < answer.size(); ++i) {
        
                mode[i] = answer.get(i);
            }
            return mode;
        }
    
        public void dfs(TreeNode o) {
        
            if (o == null) {
        
                return;
            }
            dfs(o.left);
            update(o.val);
            dfs(o.right);
        }
    
        public void update(int x) {
        
            if (x == base) {
        
                ++count;
            } else {
        
                count = 1;
                base = x;
            }
            if (count == maxCount) {
        
                answer.add(base);
            }
            if (count > maxCount) {
        
                maxCount = count;
                answer.clear();
                answer.add(base);
            }
        }
    }

#### [二叉树中和为某一值的路径][Link 10] ####

class Solution {
        
        LinkedList<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>(); 
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
            recur(root, sum);
            return res;
        }
        void recur(TreeNode root, int tar) {
        
            if(root == null) return;
            path.add(root.val);
            tar -= root.val;
            if(tar == 0 && root.left == null && root.right == null)
                res.add(new LinkedList(path));
            recur(root.left, tar);
            recur(root.right, tar);
            path.removeLast();
        }
    }

#### [两棵二叉搜索树中的所有元素][Link 11] ####

方法一 前序遍历+排序

public class Problem02 {
    
        private List<Integer> ansList;
    
        private void dfs(TreeNode root) {
            if (root == null) {
                return;
            }
    
            ansList.add(root.val);
            dfs(root.left);
            dfs(root.right);
        }
    
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            ansList = new ArrayList<>();
            dfs(root1);
            dfs(root2);
            Collections.sort(ansList);
            return ansList;
        }
    
    }

方法二 分别中序遍历+归并

public class Problem02_1 {
    
        private void dfs(TreeNode root, List<Integer> ansList) {
            if (root == null) {
                return;
            }
    
            dfs(root.left, ansList);
            ansList.add(root.val);
            dfs(root.right, ansList);
        }
    
        private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
            List<Integer> ansList = new ArrayList<>();
            int size1 = list1.size();
            int size2 = list2.size();
            int index1, index2;
            for (index1 = 0, index2 = 0; index1 < size1 && index2 < size2;) {
                int num1 = list1.get(index1);
                int num2 = list2.get(index2);
                if (num1 < num2) {
                    ansList.add(num1);
                    index1++;
                } else {
                    ansList.add(num2);
                    index2++;
                }
            }
    
            while (index1 < size1) {
                ansList.add(list1.get(index1++));
            }
    
            while (index2 < size2) {
                ansList.add(list2.get(index2++));
            }
    
            return ansList;
        }
    
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            List<Integer> ansList1 = new ArrayList<>();
            List<Integer> ansList2 = new ArrayList<>();
            dfs(root1, ansList1);
            dfs(root2, ansList2);
    
            return merge(ansList1, ansList2);
        }
    
    }

方法三 遍历+优先队列

public class Problem02_2 {
    
        private PriorityQueue<Integer> priorityQueue;
    
        private void dfs(TreeNode root) {
            if (root == null) {
                return;
            }
    
            priorityQueue.offer(root.val);
            dfs(root.left);
            dfs(root.right);
        }
    
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            priorityQueue = new PriorityQueue<>();
            dfs(root1);
            dfs(root2);
            List<Integer> ansList = new ArrayList<>();
            while (!priorityQueue.isEmpty()) {
                ansList.add(priorityQueue.poll());
            }
            return ansList;
        }
    
    }

#### [二叉树的所有路径][Link 12] ####

方法一：深度优先搜索

class Solution {
        
        public List<String> binaryTreePaths(TreeNode root) {
        
            List<String> paths = new ArrayList<String>();
            constructPaths(root, "", paths);
            return paths;
        }
    
        public void constructPaths(TreeNode root, String path, List<String> paths) {
        
            if (root != null) {
        
                StringBuffer pathSB = new StringBuffer(path);
                pathSB.append(Integer.toString(root.val));
                if (root.left == null && root.right == null) {
          // 当前节点是叶子节点
                    paths.add(pathSB.toString());  // 把路径加入到答案中
                } else {
        
                    pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                    constructPaths(root.left, pathSB.toString(), paths);
                    constructPaths(root.right, pathSB.toString(), paths);
                }
            }
        }
    }

方法二：广度优先搜索

class Solution {
        
        public List<String> binaryTreePaths(TreeNode root) {
        
            List<String> paths = new ArrayList<String>();
            if (root == null) {
        
                return paths;
            }
            Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
            Queue<String> pathQueue = new LinkedList<String>();
    
            nodeQueue.offer(root);
            pathQueue.offer(Integer.toString(root.val));
    
            while (!nodeQueue.isEmpty()) {
        
                TreeNode node = nodeQueue.poll(); 
                String path = pathQueue.poll();
    
                if (node.left == null && node.right == null) {
        
                    paths.add(path);
                } else {
        
                    if (node.left != null) {
        
                        nodeQueue.offer(node.left);
                        pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                    }
    
                    if (node.right != null) {
        
                        nodeQueue.offer(node.right);
                        pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                    }
                }
            }
            return paths;
        }
    }

#### [检查平衡性][Link 13] ####

class Solution {
        
        private boolean balanced = true;    // 默认是平衡的
        public boolean isBalanced(TreeNode root) {
        
            treeDepth(root);
            return balanced;
        }
        /*
            使用DFS计算以root为根的树的高度
            DFS的优点是最多访问所有节点一次
            先判断子树的平衡性，如果子树不平衡则说明整棵树是不平衡的，提前终止遍历
        */
        public int treeDepth(TreeNode root) {
        
            // 空树的高度为0
            // !balanced返回0完全是为了终止递归，其实返回什么无所谓
            if (root == null || !balanced) {
            
                return 0;
            }
            int leftTreeDepth = treeDepth(root.left);       // 左子树高度
            int rightTreeDepth = treeDepth(root.right);     // 右子树高度
            // 平衡性判断
            if (Math.abs(leftTreeDepth - rightTreeDepth) > 1) {
        
                balanced = false;
            }
            // root树的高度应该是左右子树较大者 + 1
            return Math.max(leftTreeDepth, rightTreeDepth) + 1;
        }
    }
    //方法二：
    class Solution {
        
        public boolean isBalanced(TreeNode root) {
        
            // 根结点为null，说明是棵空树，认为是平衡的
            if (root == null) {
        
                return true;
            }
            int leftTreeDepth = treeDepth(root.left);   // 左子树高度
            int rightTreeDepth = treeDepth(root.right); // 右子树高度
            if (Math.abs(leftTreeDepth - rightTreeDepth) > 1) {
        
                return false;   // 高度差大于1说明不平衡
            }
            // 若以当前节点为根的子树是平衡的，继续递归检查它左右子树的平衡性
            return isBalanced(root.left) && isBalanced(root.right); 
        }
        public int treeDepth(TreeNode root) {
        
            // 递归出口，空树的高度为0
            if (root == null) {
        
                return 0;
            }
            // 当前二叉树的高度 = max(左子树高度,右子树高度) + 1
            return Math.max(treeDepth(root.left), treeDepth(root.right)) + 1;
        }
    }

#### [ 在每个树行中找最大值][Link 14] ####

方法一：宽度优先搜索

public List<Integer> largestValues(TreeNode root) {
        
        //LinkedList实现队列
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> values = new ArrayList<>();
        if (root != null)
            queue.add(root);//入队
        while (!queue.isEmpty()) {
        
            int max = Integer.MIN_VALUE;
            int levelSize = queue.size();//每一层的数量
            for (int i = 0; i < levelSize; i++) {
        
                TreeNode node = queue.poll();//出队
                max = Math.max(max, node.val);//记录每层的最大值
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            values.add(max);
        }
        return values;
    }

方法二：深度优先搜索

public List<Integer> largestValues(TreeNode root) {
        
        List<Integer> res = new ArrayList<>();
        helper(root, res, 1);
        return res;
    }
    //level表示的是第几层，集合res中的第一个数据表示的是
    // 第一层的最大值，第二个数据表示的是第二层的最大值……
    private void helper(TreeNode root, List<Integer> res, int level) {
        
        if (root == null)
            return;
        //如果走到下一层了直接加入到集合中
        if (level == res.size() + 1) {
        
            res.add(root.val);
        } else {
        
            //注意：我们的level是从1开始的，也就是说root
            // 是第一层，而集合list的下标是从0开始的，
            // 所以这里level要减1。
            // Math.max(res.get(level - 1), root.val)表示的
            // 是遍历到的第level层的root.val值和集合中的第level
            // 个元素的值哪个大，就要哪个。
            res.set(level - 1, Math.max(res.get(level - 1), root.val));
        }
        //下面两行是DFS的核心代码
        helper(root.left, res, level + 1);
        helper(root.right, res, level + 1);
    }

#### [二叉树的层平均值][Link 15] ####

方法一：深度优先搜索

class Solution {
        
        public List<Double> averageOfLevels(TreeNode root) {
        
            List<Integer> counts = new ArrayList<Integer>();
            List<Double> sums = new ArrayList<Double>();
            dfs(root, 0, counts, sums);
            List<Double> averages = new ArrayList<Double>();
            int size = sums.size();
            for (int i = 0; i < size; i++) {
        
                averages.add(sums.get(i) / counts.get(i));
            }
            return averages;
        }
    
        public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
        
            if (root == null) {
        
                return;
            }
            if (level < sums.size()) {
        
                sums.set(level, sums.get(level) + root.val);
                counts.set(level, counts.get(level) + 1);
            } else {
        
                sums.add(1.0 * root.val);
                counts.add(1);
            }
            dfs(root.left, level + 1, counts, sums);
            dfs(root.right, level + 1, counts, sums);
        }
    }

方法二：广度优先搜索

class Solution {
        
        public List<Double> averageOfLevels(TreeNode root) {
        
            List<Double> averages = new ArrayList<Double>();
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                double sum = 0;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    sum += node.val;
                    TreeNode left = node.left, right = node.right;
                    if (left != null) {
        
                        queue.offer(left);
                    }
                    if (right != null) {
        
                        queue.offer(right);
                    }
                }
                averages.add(sum / size);
            }
            return averages;
        }
    }

#### [从上到下打印二叉树][Link 16] ####

class Solution {
        
        public int[] levelOrder(TreeNode root) {
        
            if(root == null) return new int[0];
            Queue<TreeNode> queue = new LinkedList<>(){
        {
         add(root); }};
            ArrayList<Integer> ans = new ArrayList<>();
            while(!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                ans.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            int[] res = new int[ans.size()];
            for(int i = 0; i < ans.size(); i++)
                res[i] = ans.get(i);
            return res;
        }
    }

#### [二叉搜索树中的搜索][Link 17] ####

方法一：递归

//递归 
    public TreeNode searchBST(TreeNode root, int val) {
         
        if (root == null) 
            return null; 
        if (root.val > val) {
         
            return searchBST(root.left, val);    
        } else if (root.val < val) {
        
            return searchBST(root.right, val);
        } else {
        
            return root;
        }
    }

方法二：迭代

//迭代
    public TreeNode searchBST(TreeNode root, int val) {
        
            while (root != null) {
        
                if (root.val == val) {
        
                    return root;
                } else if (root.val > val) {
        
                    root = root.left;
                } else {
        
                    root = root.right;
                }
            }
            return null;
     }

#### [最小高度树][Link 18] ####

class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
        
            return helper(nums, 0, nums.length - 1);
        }
    
        public TreeNode helper(int[] nums, int low, int high) {
        
            if (low > high) {
           // low > high表示子数组为空
                return null;
            }
            // 以mid作为根节点
            int mid = (high - low) / 2 + low;
            TreeNode root = new TreeNode(nums[mid]);
            // 左子数组[low, mid -1]构建左子树
            root.left = helper(nums, low, mid - 1);
            // 右子数组[mid + 1, high]构建右子树
            root.right = helper(nums,mid + 1, high);
            return root;
        }
    }

#### [前序遍历构造二叉搜索树][Link 19] ####

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode bstFromPreorder(int[] preorder) {
        
            if(preorder == null || preorder.length == 0) return null;
            Stack<TreeNode> stack = new Stack();
            TreeNode root = new TreeNode(preorder[0]);
            stack.add(root);    // 根压栈
            for (int i = 1; i < preorder.length; i ++){
        
                TreeNode node = stack.peek();   // 当前节点
                if (node.val > preorder[i]){
            // 新的数据小于当前节点
                    node.left = new TreeNode(preorder[i]);  // 新的节点放左边
                    stack.add(node.left);   // 压栈
                }else{
        
                    // 往上找，找到第一个比新数据小的
                    while(!stack.isEmpty() && stack.peek().val < preorder[i]) node = stack.pop();
                    node.right = new TreeNode(preorder[i]); 
                    stack.add(node.right);
                }
            }
            return root;
        }
    }

#### [序列化和反序列化二叉搜索树][Link 20] ####

class Codec {
        
        // Encodes a tree to a single string.
        //BST的前序遍历结果
        public String serialize(TreeNode root) {
        
            if (root == null) return "";
            StringBuilder sb = new StringBuilder();
            helper(root, sb);
            return sb.substring(0, sb.length() - 1);
        }
    
        private void helper(TreeNode root, StringBuilder sb) {
        
            if (root == null) return;
            //拼接当前节点
            sb.append(root.val).append(",");
            helper(root.left, sb);
            helper(root.right, sb);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
        
            if (data == null || data.length() == 0) return null;
            String[] arr = data.split(",");
            return builder(arr, 0, arr.length - 1);
        }
    
        private TreeNode builder(String[] arr, int lo, int hi) {
        
            if (lo > hi) return null;
            TreeNode root = new TreeNode(Integer.valueOf(arr[lo]));
            //找到第一个比首元素大的元素位置
            int index = hi + 1;
            for (int i = lo + 1; i <= hi; i++) {
        
                if (Integer.valueOf(arr[i]) > root.val) {
        
                    index = i;
                    break;
                }
            }
            //递归构建子树
            root.left = builder(arr, lo + 1, index - 1);
            root.right = builder(arr, index, hi);
            return root;
        }
    }

#### [根据前序和后序遍历构造二叉树][Link 21] ####

class Solution {
        
            public TreeNode constructFromPrePost(int[] pre, int[] post) {
        
                return helper(pre,post,0,pre.length-1,0,post.length-1);
            }
    
            public TreeNode helper(int[] pre,int[] post,int preStart,int preEnd,int postStart,int postEnd) {
        
                if(preStart>preEnd) return null;
                //找到根节点
                TreeNode root = new TreeNode(pre[preStart]);
                if(preStart==preEnd) return root;
                //找到其左子树和右子树
                int leftRootVal = pre[preStart+1];
                int i;
                for(i=postStart;i<=postEnd;i++) {
        
                    if(post[i]==leftRootVal)
                        break;
                }
                int leftlen = i - postStart + 1;
                int rightlen = postEnd-1-i;
                root.left = helper(pre,post,preStart+1,preStart+leftlen,postStart,i);
                root.right = helper(pre,post,preStart+leftlen+1,preEnd,i+1,postEnd-1);
                return root;
            }
        }

#### [从先序遍历还原二叉树][Link 22] ####

方法一：迭代

class Solution {
        
        public TreeNode recoverFromPreorder(String S) {
        
            Deque<TreeNode> path = new LinkedList<TreeNode>();
            int pos = 0;
            while (pos < S.length()) {
        
                int level = 0;
                while (S.charAt(pos) == '-') {
        
                    ++level;
                    ++pos;
                }
                int value = 0;
                while (pos < S.length() && Character.isDigit(S.charAt(pos))) {
        
                    value = value * 10 + (S.charAt(pos) - '0');
                    ++pos;
                }
                TreeNode node = new TreeNode(value);
                if (level == path.size()) {
        
                    if (!path.isEmpty()) {
        
                        path.peek().left = node;
                    }
                }
                else {
        
                    while (level != path.size()) {
        
                        path.pop();
                    }
                    path.peek().right = node;
                }
                path.push(node);
            }
            while (path.size() > 1) {
        
                path.pop();
            }
            return path.peek();
        }
    }

#### [前序和中序重建二叉树][Link 23] ####

方法一：递归

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            if (preorder == null || preorder.length == 0) {
        
                return null;
            }
            Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
            int length = preorder.length;
            for (int i = 0; i < length; i++) {
        
                indexMap.put(inorder[i], i);
            }
            TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
            return root;
        }
    
        public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
        
            if (preorderStart > preorderEnd) {
        
                return null;
            }
            int rootVal = preorder[preorderStart];
            TreeNode root = new TreeNode(rootVal);
            if (preorderStart == preorderEnd) {
        
                return root;
            } else {
        
                int rootIndex = indexMap.get(rootVal);
                int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
                TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
                TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
                root.left = leftSubtree;
                root.right = rightSubtree;
                return root;
            }
        }
    }

方法二：迭代

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            if (preorder == null || preorder.length == 0) {
        
                return null;
            }
            TreeNode root = new TreeNode(preorder[0]);
            int length = preorder.length;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            int inorderIndex = 0;
            for (int i = 1; i < length; i++) {
        
                int preorderVal = preorder[i];
                TreeNode node = stack.peek();
                if (node.val != inorder[inorderIndex]) {
        
                    node.left = new TreeNode(preorderVal);
                    stack.push(node.left);
                } else {
        
                    while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
        
                        node = stack.pop();
                        inorderIndex++;
                    }
                    node.right = new TreeNode(preorderVal);
                    stack.push(node.right);
                }
            }
            return root;
        }
    }

#### [从中序与后序遍历序列构造二叉树][Link 24] ####

递归

class Solution {
        
    
        HashMap<Integer,Integer> memo = new HashMap<>();
        int[] post;
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
        
            for(int i = 0;i < inorder.length; i++) memo.put(inorder[i], i);
            post = postorder;
            TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1);
            return root;
        }
    
        public TreeNode buildTree(int is, int ie, int ps, int pe) {
        
            if(ie < is || pe < ps) return null;
    
            int root = post[pe];
            int ri = memo.get(root);
    
            TreeNode node = new TreeNode(root);
            node.left = buildTree(is, ri - 1, ps, ps + ri - is - 1);
            node.right = buildTree(ri + 1, ie, ps + ri - is, pe - 1);
            return node;
        }
    }

class Solution {
        
        int post_idx;
        int[] postorder;
        int[] inorder;
        Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();
    
        public TreeNode helper(int in_left, int in_right) {
        
            // 如果这里没有节点构造二叉树了，就结束
            if (in_left > in_right) {
        
                return null;
            }
    
            // 选择 post_idx 位置的元素作为当前子树根节点
            int root_val = postorder[post_idx];
            TreeNode root = new TreeNode(root_val);
    
            // 根据 root 所在位置分成左右两棵子树
            int index = idx_map.get(root_val);
    
            // 下标减一
            post_idx--;
            // 构造右子树
            root.right = helper(index + 1, in_right);
            // 构造左子树
            root.left = helper(in_left, index - 1);
            return root;
        }
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
        
            this.postorder = postorder;
            this.inorder = inorder;
            // 从后序遍历的最后一个元素开始
            post_idx = postorder.length - 1;
    
            // 建立（元素，下标）键值对的哈希表
            int idx = 0;
            for (Integer val : inorder) {
        
                idx_map.put(val, idx++);
            }
            
            return helper(0, inorder.length - 1);
        }
    }

#### [左叶子之和][Link 25] ####

方法一：深度优先搜索

class Solution {
        
        public int sumOfLeftLeaves(TreeNode root) {
        
            return root != null ? dfs(root) : 0;
        }
    
        public int dfs(TreeNode node) {
        
            int ans = 0;
            if (node.left != null) {
        
                ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
            }
            if (node.right != null && !isLeafNode(node.right)) {
        
                ans += dfs(node.right);
            }
            return ans;
        }
    
        public boolean isLeafNode(TreeNode node) {
        
            return node.left == null && node.right == null;
        }
    }

方法二：广度优先搜索

class Solution {
        
        public int sumOfLeftLeaves(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            int ans = 0;
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                if (node.left != null) {
        
                    if (isLeafNode(node.left)) {
        
                        ans += node.left.val;
                    } else {
        
                        queue.offer(node.left);
                    }
                }
                if (node.right != null) {
        
                    if (!isLeafNode(node.right)) {
        
                        queue.offer(node.right);
                    }
                }
            }
            return ans;
        }
        public boolean isLeafNode(TreeNode node) {
        
            return node.left == null && node.right == null;
        }
    }

#### [二叉搜索树的最小绝对差][Link 26] ####

//保存最小差
        int min = Integer.MAX_VALUE;
    
        //上一个节点的值
        int pre = Integer.MIN_VALUE;
    
        public int getMinimumDifference(TreeNode root) {
        
            dfs(root);
            return min;
        }
    
        private void dfs(TreeNode node) {
        
            if (node != null) {
        
                dfs(node.left);
                //跳过第一个节点
                if (pre != Integer.MIN_VALUE) {
        
                    min = Math.min(node.val - pre, min);
                }
                pre = node.val;
                dfs(node.right);
            }
        }

#### [路径总和][Link 27] ####

#### [路径总和 II][II] ####

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1OTY0NTU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/d98ff56ea3a64fd99f9080fac7369474.png
[Link 1]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[Link 2]: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
[Link 3]: https://leetcode-cn.com/problems/balanced-binary-tree/
[Link 4]: https://leetcode-cn.com/problems/list-of-depth-lcci/
[Link 5]: https://leetcode-cn.com/problems/invert-binary-tree/
[Link 6]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[Link 7]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Link 8]: https://leetcode-cn.com/problems/symmetric-tree/
[Link 9]: https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
[Link 10]: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
[Link 11]: https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees/
[Link 12]: https://leetcode-cn.com/problems/binary-tree-paths/
[Link 13]: https://leetcode-cn.com/problems/check-balance-lcci/
[Link 14]: https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
[Link 15]: https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
[Link 16]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
[Link 17]: https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
[Link 18]: https://leetcode-cn.com/problems/minimum-height-tree-lcci/
[Link 19]: https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/
[Link 20]: https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
[Link 21]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
[Link 22]: https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/
[Link 23]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[Link 24]: https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[Link 25]: https://leetcode-cn.com/problems/sum-of-left-leaves/
[Link 26]: https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/
[Link 27]: https://leetcode-cn.com/problems/path-sum/
[II]: https://leetcode-cn.com/problems/path-sum-ii/