本文共 7749 字，大约阅读时间需要 25 分钟。

二叉树中的公共祖先（这个写不来）

二叉树的最大的路径和(二叉树的中随意两个节点的路径和)

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

给定有序数组:[-10,-3,0,5,9],一个可能的答案是:[ 0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

package 计算机程序算法分类.二叉树问题;/** * @Classname 数组构建二叉树 * @Description TODO * @Date 2021/5/10 19:13 * @Created by xjl */public class 数组构建二叉树 {    public class TreeNode {        int val;        TreeNode left;        TreeNode right;        TreeNode() {        }        TreeNode(int val) {            this.val = val;        }        TreeNode(int val, TreeNode left, TreeNode right) {            this.val = val;            this.left = left;            this.right = right;        }    }    public TreeNode sortedArrayToBST(int[] array, int letf, int right) {        if (letf > right) {            return null;        }        int mid = letf + (right - letf) / 2;        TreeNode root = new TreeNode(array[mid]);        root.left = sortedArrayToBST(array, letf, mid - 1);        root.right = sortedArrayToBST(array, mid + 1, right);        return root;    }}

package 计算机程序算法分类.二叉树问题;import 牛客网练习题.Solution;/** * @Classname sortedListToBST * @Description TODO * @Date 2021/5/10 19:19 * @Created by xjl */public class sortedListToBST {    public class TreeNode {        int val;        TreeNode left;        TreeNode right;        TreeNode() {        }        TreeNode(int val) {            this.val = val;        }        TreeNode(int val, TreeNode left, TreeNode right) {            this.val = val;            this.left = left;            this.right = right;        }    }    public class ListNode {        int val;        ListNode next;        ListNode() {        }        ListNode(int val) {            this.val = val;        }        ListNode(int val, ListNode next) {            this.val = val;            this.next = next;        }    }    public TreeNode sortedListToBST(ListNode head) {        return buildTree(head, null);    }    private TreeNode buildTree(ListNode left, ListNode right) {        if (left == right) {            return null;        }        ListNode mid = getMedian(left, right);        TreeNode root = new TreeNode(mid.val);        root.left = buildTree(left, mid);        root.right = buildTree(mid.next, right);        return root;    }    //这是的是的快慢指针来实现的找到链表的中中间的位置    public ListNode getMedian(ListNode left, ListNode right) {        ListNode fast = left;        ListNode slow = left;        while (fast != right && fast.next != right) {            fast = fast.next.next;            slow = slow.next;        }        return slow;    }}

package 计算机程序算法分类.二叉树问题;/** * @Classname 二叉搜索树的转为双链表 * @Description TODO * @Date 2021/5/10 19:31 * @Created by xjl */public class 二叉搜索树的转为双链表 {    class Node {        public int val;        public Node left;        public Node right;        public Node() {        }        public Node(int _val) {            val = _val;        }        public Node(int _val, Node _left, Node _right) {            val = _val;            left = _left;            right = _right;        }    }    Node pre, head;    /**     * @description TODO  本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。      * @param: root     * @date: 2021/5/10 19:37     * @return: 计算机程序算法分类.二叉树问题.二叉搜索树的转为双链表.Node     * @author: xjl    */    public Node treeToDoublyList(Node root) {        if (root == null) {            return null;        }        dfs(root);        head.left = pre;        pre.right = head;        return head;    }    void dfs(Node cur) {        if (cur == null) {            return;        }        dfs(cur.left);        if (pre != null) {            pre.right = cur;        } else {            head = cur;        }        cur.left = pre;        pre = cur;        dfs(cur.right);    }}

给定一个有相同值的二叉搜索树（BST)，找出 BST中的所有众数（出现频率最高的元素)。

假定BST有如下定义:

1. ·结点左子树中所含结点的值小于等于当前结点的值
2. 结点右子树中所含结点的值大于等于当前结点的值·
3. 左子树和右子树都是二叉搜索树

这题是让求二叉搜索树中的众数，也就是出现次数最多的那个数。如果是在一个排序的数组中找众数，这个可能就比较简单，但这题是让在二叉搜索树中查找。我们都知道二叉搜索树的中序遍历是有序的，有一种方式就是先把二叉搜索树中序遍历的结果存放到一个数组中，因为这个数组是升序的（虽然有重复的)，我们可以遍历这个数组，这里使用几个变量。使用变量curent表示当前的值，count表示当前值的数量，maxCount表示重复数字最大的数量。list集合存放结果。

在数组中求解众数的时候的可以采用的多种方法

package 计算机程序算法分类.二叉树问题;import org.junit.Test;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * @Classname 二叉搜索树的众数 * @Description TODO * @Date 2021/4/30 15:13 * @Created by xjl */public class 二叉搜索树的众数 {    public class TreeNode {        int val;        TreeNode left;        TreeNode right;        TreeNode(int x) {            val = x;        }    }    public int[] findMode(TreeNode root) {        ArrayList
   
     list = new ArrayList<>();        //中序遍历        dfs(root, list);        int[] arr = list.stream().mapToInt(Integer::intValue).toArray();        int count = 0;        int maxcount = 0;        int left = 0;        int right = 0;        ArrayList
    
      res = new ArrayList<>();        while (left < arr.length && right < arr.length) {            while (right < arr.length && arr[left] == arr[right]) {                count++;                right++;            }            if (maxcount < count) {                maxcount = count;                if (res.size() != 0) {                    res.remove(res.size() - 1);                }                res.add(arr[left]);            } else if (maxcount == count) {                maxcount = count;                res.add(arr[left]);            }            count = 0;            left = right;        }        return res.stream().mapToInt(Integer::intValue).toArray();    }    private void dfs(TreeNode root, ArrayList
     
       list) {        if (root == null) {            return;        }        if (root.left != null) {            dfs(root.left, list);        }        list.add(root.val);        if (root.right != null) {            dfs(root.right, list);        }    }    public int[] test11(int[] arr) {        int count = 0;        int maxcount = 0;        int left = 0;        int right = 0;        ArrayList
      
        res = new ArrayList<>();        //使用的滑动窗口        while (left < arr.length && right < arr.length) {            while (right < arr.length && arr[left] == arr[right]) {                count++;                right++;            }            if (maxcount < count) {                maxcount = count;                res.clear();                res.add(arr[left]);            } else if (maxcount == count) {                maxcount = count;                res.add(arr[left]);            }            count = 0;            left = right;        }        return res.stream().mapToInt(Integer::intValue).toArray();    }    @Test    public void test() {        int[] arr = new int[]{4, 3, 6, 2, 4, 6, 7, 4, 4, 6};        Arrays.sort(arr);        int[] ints = test11(arr);        System.out.println(Arrays.toString(ints).toString());    }}
      
     
    
   

求解二叉树的最小深度

这题其实不难，看到这道题我们首先想到的是BFS，就是一层一层的遍历，如果某一层的某个节点没有子节点了，我们就返回这个节点的层数即可。

我们还可以使用递归的方式，返回Math.min(左子树的深度，右子树的深度)+1，看起来很有道理，但有一个问题，如果左右子树都不为空或者都为空定汶回题的。但如果左右子树一个为空一个不为空，就会有问题了，因为为空的那个子节点的深

每一行的树的的最大值

可以采用的是BFS哎求解。保证在遍历的时候获取最大的值就行。层序遍历

除了一层一层遍历以外，我们还可以使用DFS（深度优先搜索算法）来求解。我们就以上面的举例来画个图分析一下

二叉树的路径和

路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

这道题要求的最大路径和如果是从根节点开始到叶子节点就好办了，我们可以通过递归的方式，从下往上，舍去比较小的路径节点，保留比较大的节点。但这道题要求的最大路径和并不一定经过根节点，如果再使用上面的方式就行不通了，对于这道题我们可以分为4种情况来讨论

1，只要当前节点，舍弃子节点。比如下面结点2的左右子节点都是负数，如果是负数我们还不如不要，所以直接舍弃子节点。

 2，保留当前节点和左子节点。比如下面结点2的右子节点是负数，我们直接舍弃右子节点，但左子节点不是负数，我们可以保留左子节点。

3，保留当前节点和右子节点。比如下面结点2的左子节点是负数，我们直接舍弃左子节点，但右子节点不是负数，我们可以保留右子节点。

4，保留当前节点和两个子节点。比如下面结点2的左右子节点都不是负数，我们都可以留下。

上面的1，2，3都可以作为子树的一部分再继续计算，我们可以使用同一个公式，取左右子节点最大的那个即可，如果都小于0我们不要了，下面公式中left是左子树的值，right是右子树的值

int res = root.val + Math.max (0，Math.max(left, right) ) ;

而4是不能在作为子树的一部分参与计算的，因为已经分叉了，比如下面的3→2→4是不能再和结点1进行组合的。第4种情况如果左右子树有一个是小于0的我们还不如不选，如果都大于0我们都要选的。

int cur = root.val + Math.max(0，left) + Math.max (0,right) ;

转载地址：http://bcltz.baihongyu.com/