二叉树

基础知识

二叉树的种类

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树

满二叉树

满二叉树：如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。

这棵二叉树为满二叉树，也可以说深度为 k，有$2^{k-1}$个节点的二叉树。

完全二叉树

完全二叉树的定义：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h 从 1 开始），则该层包含 $1-2^{(h-1)}$ 个节点。

优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

下面这两棵树都是搜索树:

平衡二叉搜索树

平衡二叉搜索树：又被称为 AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

如图：

最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了 1。

C++中 map、set、multimap，multiset 的底层实现都是平衡二叉搜索树，所以 map、set 的增删操作时间时间复杂度是$logn$，而 unordered_map、unordered_set，unordered_map、unordered_set 底层实现是哈希表。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

链式存储如图：

顺序存储（用数组来存储二叉树）的方式如图：

用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 $i\ast 2+1$，右孩子就是 $i\ast 2+2$。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

所以大家要了解，用数组依然可以表示二叉树。

二叉树的遍历方式

主要有两种遍历方式：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
2. 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

• 深度优先遍历
  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）
• 广度优先遍历
  • 层次遍历（迭代法）

在深度优先遍历中：有三个顺序，前中后序遍历，这里前中后，其实指的就是中间节点的遍历顺序。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

• 前序遍历：中左右
• 中序遍历：左中右
• 后序遍历：左右中

深度优先和广度优先的遍历方式：

• 二叉树相关题目中，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。之前说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
• 而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

二叉树的定义

链式存储的二叉树节点的定义方式。

C++代码如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

java 代码：

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;
    }
}

二叉树的定义和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子。

二叉树的递归遍历

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

给你二叉树的根节点 root ，返回它节点值的 前序、中序和后序 遍历。

解答：

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }
    public void preorder(TreeNode root, List<Integer> result) {
        if(root == null) return;
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    public void inorder(TreeNode root, List<Integer> result){
        if(root == null) return;
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}

//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    public void postorder(TreeNode root, List<Integer> result){
        if(root == null) return;
        postorder(root.left, result);
        postorder(root.right, result);
        result.add(root.val);
    }
}

二叉树的迭代遍历

解答：

//迭代前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.addFirst(root);
        while(!deque.isEmpty()){
            TreeNode temp = deque.poll();
            if(temp.right != null) deque.addFirst(temp.right);
            if(temp.left != null) deque.addFirst(temp.left);
            res.add(temp.val);
        }
        return res;
    }
}

//迭代后序循环遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.addFirst(root);
        while(!deque.isEmpty()){
            TreeNode temp = deque.poll();
            if(temp.left != null) deque.addFirst(temp.left);
            if(temp.right != null) deque.addFirst(temp.right);
            res.add(temp.val);
        }
        Collections.reverse(res);//翻转
        return res;
    }
}

//迭代中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.addFirst(root);

        while(!deque.isEmpty()){
            TreeNode temp = deque.peek();
            while(temp.left != null){
                deque.addFirst(temp.left);
                temp = temp.left;
            }
            while(deque.peek().right == null){
                res.add(deque.poll().val);
                if(deque.peek() == null) return res;
            }

            res.add(deque.peek().val);
            deque.addFirst(deque.poll().right);
        }
        return res;
    }
}

统一迭代法

将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。

解答：

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.addFirst(root);

        while(!deque.isEmpty()){
            TreeNode node = deque.peek();
            res.add(deque.poll().val);
            if(node.right != null){
                deque.addFirst(node.right);
            }
            if(node.left != null){
                deque.addFirst(node.left);
            }
        }
        return res;
    }
}

//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.addFirst(root);

        while(!deque.isEmpty()){
            TreeNode node = deque.peek();
            if(node != null){
                deque.poll();
                if(node.right != null){
                    deque.addFirst(node.right);
                }
                deque.addFirst(node);
                deque.addFirst(null);
                if(node.left != null){
                    deque.addFirst(node.left);
                }
            } else{
                deque.poll();
                if(deque.peek() != null) res.add(deque.poll().val);
            }
        }
        return res;
    }
}

//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.addFirst(root);

        while(!deque.isEmpty()){
            TreeNode node = deque.peek();
            if(node != null){
                deque.addFirst(null);
                if(node.right != null){
                    deque.addFirst(node.right);
                }
                if(node.left != null){
                    deque.addFirst(node.left);
                }

            } else{
                deque.poll();
                if(deque.peek() != null) res.add(deque.poll().val);
            }
        }
        return res;
    }
}

二叉树层序遍历

102.二叉树的层序遍历

力扣题目链接

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

解答：

class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        checknode(root, 0);
        // checknode1(root);
        return resList;
    }
    //BFS 递归
    private void checknode(TreeNode node, int deep){
        if(node == null) return;
        deep++;
        if(resList.size() < deep){
            List<Integer> temp = new ArrayList<>();
            resList.add(temp);
        }
        resList.get(deep-1).add(node.val);
        checknode(node.left, deep);
        checknode(node.right, deep);
    }

    //BFS 迭代
    private void checknode1(TreeNode node){
        if(node == null) return;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(node);

        while(!deque.isEmpty()){
            int len = deque.size();
            List<Integer> temp = new ArrayList<>();
            while(len > 0){
                if(deque.peek().left != null) deque.offer(deque.peek().left);
                if(deque.peek().right != null) deque.offer(deque.peek().right);
                len--;
                temp.add(deque.poll().val);
            }
            resList.add(temp);
        }

    }
}

107.二叉树的层次遍历 II

力扣题目链接

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

解答：

class Solution {
    List<List<Integer>> resList = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // checknode(root, 0);
        // List<List<Integer>> res = new ArrayList<>();
        // for(int i = resList.size()-1; i >= 0; i--){
        //     res.add(resList.get(i));
        // }
        checknode1(root);
        return resList;
    }
    //递归
    private void checknode(TreeNode node, int deep){
        if(node == null) return;
        deep++;
        if(resList.size() < deep){
            List<Integer> temp = new ArrayList<>();
            resList.add(temp);
        }
        resList.get(deep-1).add(node.val);
        checknode(node.left, deep);
        checknode(node.right, deep);
    }
    //迭代
    private void checknode1(TreeNode node){
        if(node == null) return;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(node);

        while(!deque.isEmpty()){
            int len = deque.size();
            List<Integer> temp = new ArrayList<>();
            while(len > 0){
                if(deque.peek().left != null) deque.offer(deque.peek().left);
                if(deque.peek().right != null) deque.offer(deque.peek().right);
                len--;
                temp.add(deque.poll().val);
            }
            resList.addFirst(temp);//新遍历到的层插到头部, 这样就满足按照层次反序的要求
        }

    }
}

199.二叉树的右视图

力扣题目链接

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解答：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.offer(root);
        int deep = 0;
        while(!deque.isEmpty()){
            int len = deque.size();
            res.add(deque.peekLast().val);
            while(len > 0){
                len--;
                if(deque.peek().left != null) deque.offer(deque.peek().left);
                if(deque.peek().right != null) deque.offer(deque.peek().right);
                deque.poll();
            }
        }
        return res;
    }
}

637.二叉树的层平均值

力扣题目链接

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

解答：

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.offer(root);
        int deep = 0;
        double sum = (double)root.val;
        while(!deque.isEmpty()){
            int len = deque.size();
            res.add(sum/len);
            sum = 0;
            while(len > 0){
                len--;
                if(deque.peek().left != null){
                    deque.offer(deque.peek().left);
                    sum += deque.peek().left.val;
                }
                if(deque.peek().right != null){
                    deque.offer(deque.peek().right);
                    sum += deque.peek().right.val;
                }
                deque.poll();
            }
        }
        return res;
    }
}

429.N 叉树的层序遍历

力扣题目链接

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

解答：

class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(Node root) {
        checknode(root, 0);
        // checknode1(root);//迭代的写法类似
        return resList;
    }
    //BFS 递归
    private void checknode(Node node, int deep){
        if(node == null) return;
        deep++;
        if(resList.size() < deep){
            List<Integer> temp = new ArrayList<>();
            resList.add(temp);
        }
        resList.get(deep-1).add(node.val);
        for(Node a : node.children){
            checknode(a, deep);
        }
    }
}

515.在每个树行中找最大值

力扣题目链接

您需要在二叉树的每一行中找到最大的值。

解答：

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return res;
        deque.offer(root);
        int max_num = root.val;
        while(!deque.isEmpty()){
            int len = deque.size();
            res.add(max_num);
            max_num = Integer.MIN_VALUE;
            while(len > 0){
                len--;
                if(deque.peek().left != null){
                    deque.offer(deque.peek().left);
                    max_num = max_num > deque.peek().left.val ? max_num : deque.peek().left.val;
                }
                if(deque.peek().right != null){
                    deque.offer(deque.peek().right);
                    max_num = max_num > deque.peek().right.val ? max_num : deque.peek().right.val;
                }
                deque.poll();
            }
        }
        return res;
    }
}

116.填充每个节点的下一个右侧节点指针

力扣题目链接

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解答：

class Solution {
    public Node connect(Node root) {
        Deque<Node> deque = new LinkedList<>();
        if(root == null) return root;
        deque.offer(root);
        while(!deque.isEmpty()){
            int len = deque.size();
            Node cur = deque.poll();
            if(cur.left != null) deque.offer(cur.left);
            if(cur.right != null) deque.offer(cur.right);
            len--;
            while(len > 0){
                len--;
                Node next = deque.poll();
                if(next.left != null) deque.offer(next.left);
                if(next.right != null) deque.offer(next.right);

                cur.next = next;
                cur = next;
            }
            cur.next = null;
        }
        return root;
    }
}

117.填充每个节点的下一个右侧节点指针 II

力扣题目链接

解答和上一题一样

104.二叉树的最大深度

力扣题目链接

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

中前后是求高度的逻辑，前后中是求深度的逻辑

//递归
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)); + 1;
    }
}
//递归法(求深度法)
class Solution {
    public int res = 0;
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        ans(root, 0);
        return res;
    }
    private void ans(TreeNode node, int temp){
        if(node == null) return;
        temp++;
        if(res < temp) res = temp;
        ans(node.left, temp);
        ans(node.right, temp);

    }
}

//深度回溯
class Solution {
    public int res = 0;
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        ans(root, 1);
        return res;
    }
    private void ans(TreeNode node, int temp){
        res = res > temp ? res : temp;
        if(node.left == null && node.right == null) return;
        if(node.left != null) ans(node.left, temp+1);

        if(node.right != null) ans(node.right, temp+1);

    }
}

//迭代
class Solution {
    public int maxDepth(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        int res = 0;
        if(root == null) return res;
        deque.offer(root);
        while(!deque.isEmpty()){
            int len = deque.size();

            while(len > 0){
                len--;
                TreeNode temp = deque.poll();
                if(temp.left != null) deque.offer(temp.left);
                if(temp.right != null) deque.offer(temp.right);
            }
            res++;
        }
        return res;
    }
}

111.二叉树的最小深度

力扣题目链接

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

//递归
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        if(root.left != null && root.right != null) return 1 + Math.min(minDepth(root.left),minDepth(root.right));
        else if(root.left == null) return 1 + minDepth(root.right);
        else return 1 + minDepth(root.left);
    }
}

//迭代
class Solution {
    public int minDepth(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        int res = 0;
        if(root == null) return res;
        deque.offer(root);
        res++;
        while(!deque.isEmpty()){
            int len = deque.size();
            while(len > 0){
                len--;
                TreeNode temp = deque.poll();
                if(temp.left != null) deque.offer(temp.left);
                if(temp.right != null) deque.offer(temp.right);
                if(temp.left != null || temp.right != null){}
                else return res;
            }
            res++;
        }
        return res;
    }
}

226.翻转二叉树

力扣题目链接

翻转一棵二叉树。

解答：

//递归
/**
     * 前后序遍历都可以
     * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
     */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

//迭代
class Solution {
    public TreeNode invertTree(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        if(root == null) return root;
        deque.push(root);

        while(!deque.isEmpty()){
            int len = deque.size();
            while(len-- > 0){
                TreeNode temp = deque.pop();
                swapChildren(temp);
                if(temp.left != null) deque.offer(temp.left);
                if(temp.right != null) deque.offer(temp.right);
            }
        }
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

101. 对称二叉树

力扣题目链接

给定一个二叉树，检查它是否是镜像对称的。

解答：

//递归
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return checknode(root.left, root.right);
    }
    private boolean checknode(TreeNode node1, TreeNode node2){
        if(node1 != null && node2 != null){
            return node1.val == node2.val && checknode(node1.left, node2.right) && checknode(node1.right, node2.left);
        }
        else if(node1 == null && node2 == null) return true;
        else return false;
    }
}

//迭代
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        boolean res = false;
        if(root == null) return res;
        deque.offer(root.right);
        deque.addFirst(root.left);
        while(!deque.isEmpty()){
            TreeNode leftnode = deque.poll();
            TreeNode rightnode = deque.pollLast();
            if(leftnode == null && rightnode == null) continue;
            if(leftnode == null || rightnode == null || leftnode.val != rightnode.val) return false;
            deque.addFirst(leftnode.left);
            deque.addLast(rightnode.right);
            deque.addFirst(leftnode.right);
            deque.addLast(rightnode.left);
        }
        return true;
    }
}

类似题目

100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解答：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return checknode(p, q);
    }
    private boolean checknode(TreeNode node1, TreeNode node2){
        if(node1 != null && node2 != null){
            return node1.val == node2.val && checknode(node1.left, node2.left) && checknode(node1.right, node2.right);
        }
        else if(node1 == null && node2 == null) return true;
        else return false;
    }
}

572.另一个树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

解答：

//dfs递归
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot);
    }
    private boolean dfs(TreeNode node1, TreeNode node2){
        if(node1 == null || node2 == null) return false;

        return checknode(node1, node2) || dfs(node1.left, node2) || dfs(node1.right, node2);
    }
    private boolean checknode(TreeNode node1, TreeNode node2){
        if(node1 != null && node2 != null){
            return node1.val == node2.val && checknode(node1.left, node2.left) && checknode(node1.right, node2.right);
        }
        else if(node1 == null && node2 == null) return true;
        else return false;
    }
}

222.完全二叉树的节点个数

力扣题目链接

给出一个完全二叉树，求出该树的节点个数。

解答：

//迭代
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
//满二叉树
class Solution {
    /**
     * 针对完全二叉树的解法
     *
     * 满二叉树的结点数为：2^depth - 1
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left != null) {  // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) { // 求右子树深度
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

110.平衡二叉树

力扣题目链接

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

解答：

//递归1
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return compare(root.left, root.right);
    }
    private boolean compare(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 == null) return true;
        if(Math.abs(getHight(node1) - getHight(node2)) > 1) return false;
        if(node1 == null || node2 == null) return true;
        return compare(node1.left, node1.right) && compare(node2.left, node2.right);
    }
    private int getHight(TreeNode node){
        if(node == null) return 0;
        return Math.max(getHight(node.left), getHight(node.right)) + 1;
    }
}

//递归2
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return getHight(root) != -1;
    }
    private int getHight(TreeNode node){
        if(node == null) return 0;
        int lefthight = getHight(node.left);
        if(lefthight == -1) return -1;
        int righthight = getHight(node.right);
        if(righthight == -1) return -1;
        if(Math.abs(righthight - lefthight) > 1) return -1;

        return Math.max(lefthight, righthight) + 1;
    }
}

257. 二叉树的所有路径

力扣题目链接

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

解答：

//递归1
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        List<Integer> paths = new  ArrayList<>();
        traversal(root, paths, res);
        return res;
    }
    private void traversal(TreeNode node, List<Integer> paths, List<String> res){
        paths.add(node.val);//前序遍历
        if(node.left == null && node.right == null){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));
            res.add(sb.toString());
            return;
        }
        if(node.left != null){
            traversal(node.left, paths, res);
            paths.remove(paths.size() - 1);//回溯
        }
        if(node.right != null){
            traversal(node.right, paths, res);
            paths.remove(paths.size() - 1);//回溯
        }
    }
}
//递归2
class Solution {
    public List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        deal(root, "");
        return res;
    }
    private void deal(TreeNode node, String s){
        if(node == null) return;
        int num = node.val;
        String temp = new String();
        if(node.left == null && node.right == null){
            res.add((new StringBuilder(s).append(num)).toString());
            return;
        }
        if(node.left != null){
            temp = (new StringBuilder(s).append(num).append("->")).toString();
            deal(node.left, temp);
        }
        if(node.right != null){
            temp = (new StringBuilder(s).append(num).append("->")).toString();
            deal(node.right, temp);
        }
    }
}
//递归3
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new LinkedList<>();
        if (root == null)
            return res;
        //到达叶子节点，把路径加入到集合中
        if (root.left == null && root.right == null) {
            res.add(root.val + "");
            return res;
        }
        //遍历左子节点的路径
        for (String path : binaryTreePaths(root.left)) {
            res.add(root.val + "->" + path);
        }
        //遍历右子节点的路径
        for (String path : binaryTreePaths(root.right)) {
            res.add(root.val + "->" + path);
        }
        return res;
    }
}
 //迭代
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new LinkedList<>();
        if (root == null)
            return res;
        Stack<Object> stack = new Stack<>();
        stack.push(root);
        stack.push(root.val + "");
        while(!stack.isEmpty()){
            String paths = (String) stack.pop();
            TreeNode node = (TreeNode) stack.pop();
            if(node.left == null && node.right == null){
                res.add(paths);
            }
            if(node.left != null){
                stack.push(node.left);
                stack.push(paths + "->" + node.left.val);
            }
            if(node.right != null){
                stack.push(node.right);
                stack.push(paths + "->" + node.right.val);
            }
        }
        return res;
    }
}

404.左叶子之和

力扣题目链接

计算给定二叉树的所有左叶子之和。

解答：

//递归
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        int res = 0;
        if(root.left != null && root.left.left == null && root.left.right == null) res += root.left.val;
        return res + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

//迭代
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        int res = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            TreeNode temp = deque.poll();
            if(temp.left != null){
                deque.offer(temp.left);
                if(temp.left.left == null && temp.left.right == null) res += temp.left.val;
            }
            if(temp.right != null) deque.offer(temp.right);
        }
        return res;
    }
}

513.找树左下角的值

力扣题目链接

给定一个二叉树，在树的最后一行找到最左边的值。

解答：

//递归
class Solution {
    private int Deep = -1, Value = 0;
    public int findBottomLeftValue(TreeNode root) {
        if(root == null) return 0;
        findLeftValue(root, 0);
        return Value;
    }
    private void findLeftValue(TreeNode node, int depth){
        if(node.left == null && node.left == null){
            if(depth > Deep){
                Deep = depth;
                Value = node.val;
            }
        }
        if(node.left != null) findLeftValue(node.left, depth + 1);
        if(node.right != null) findLeftValue(node.right, depth + 1);
    }
}

//迭代
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if(root == null) return 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int res = 0;
        while(!deque.isEmpty()){
            int len =deque.size();
            res = deque.peek().val;
            for(;len > 0; len--){
                TreeNode temp = deque.poll();
                if(temp.left != null) deque.offer(temp.left);
                if(temp.right != null) deque.offer(temp.right);
            }
        }
        return res;
    }
}

112. 路径总和

力扣题目链接

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

解答：

//递归
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        int temp = root.val;
        if(root.left == null && root.right == null) return temp == targetSum;
        return hasPathSum(root.left, targetSum - temp) || hasPathSum(root.right, targetSum - temp);
    }
}

类似题

113. 路径总和 ii

力扣题目链接

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

解答：

//递归
class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        traserval(root, targetSum);
        return res;
    }
    private void traserval(TreeNode node, int count){
        if(node == null) return;
        path.offer(node.val);
        count -= node.val;
        if(node.left ==null && node.right == null && count == 0){
            res.add(new LinkedList<>(path));
        }
        traserval(node.left, count);
        traserval(node.right,count);
        path.removeLast();

    }
}

106.从中序与后序遍历序列构造二叉树

力扣题目链接

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

解答：

class Solution {
    private Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }

        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder,int postBegin, int postEnd){
        if(inBegin >= inEnd || postBegin >= postEnd){
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfLeft = rootIndex - inBegin;
        root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;

    }
}

类似题

105.从前序与中序遍历序列构造二叉树

力扣题目链接

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

解答：

class Solution {
    private Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }

        return findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);
    }
    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder,int preBegin, int preEnd){
        if(inBegin >= inEnd || preBegin >= preEnd){
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfLeft = rootIndex - inBegin;
        root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin + 1, preBegin + lenOfLeft + 1);
        root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenOfLeft + 1, preEnd);
        return root;

    }
}

654.最大二叉树

力扣题目地址

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

• 二叉树的根是数组中的最大元素。
• 左子树是通过数组中最大值左边部分构造出的最大二叉树。
• 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

解答：

//递归
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums.length == 0) return null;
        return construct(nums, 0, nums.length);
    }
    private TreeNode construct(int[] nums, int left, int right){
        if(right <= left) return null;
        int max_num = left;
        for(int i = left+1; i < right; i++){
            if(nums[max_num] < nums[i]) max_num = i;
        }
        TreeNode node = new TreeNode(nums[max_num]);
        node.left = construct(nums, left, max_num);
        node.right = construct(nums, max_num+1, right);
        return node;
    }
}
//迭代
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums == null && nums.length == 0) return null;
        Deque<TreeNode> deque = new LinkedList<>();
        for(int i : nums){
            TreeNode cur = new TreeNode(i);

            while(!deque.isEmpty() && deque.peek().val < i){
                TreeNode node = deque.pop();
                if(deque.isEmpty()){
                    cur.left = node;
                } else {
                    TreeNode top = deque.peek();
                    if(top.val > i) cur.left = node;
                }
            }
            if(!deque.isEmpty()) deque.peek().right = cur;
            deque.push(cur);
        }
        while(deque.size() > 1) deque.pop();

        return deque.pop();
    }
}

617.合并二叉树

力扣题目链接

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

解答：

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;

    }
}

700.二叉搜索树中的搜索

力扣题目地址

给定二叉搜索树（BST）的根节点和一个值。 你需要在 BST 中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

解答：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) return root;
        TreeNode node = searchBST(root.left, val);
        if(node != null) return node;
        return searchBST(root.right, val);
    }
}

//利用BST的性质优化
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) return root;
        if(root.val > val) return searchBST(root.left, val);
        else return searchBST(root.right, val);

    }
}

98.验证二叉搜索树

力扣题目链接

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

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

解答：

class Solution {
    public boolean isValidBST(TreeNode root) {
        return checkNode(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean checkNode(TreeNode node, long left, long right){
        if(node == null) return true;
        if(node.val >= right || node.val <= left) return false;
        return checkNode(node.left, left, node.val) && checkNode(node.right, node.val, right);
    }
}

530.二叉搜索树的最小绝对差

力扣题目链接

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

解答：

//中序递归
class Solution {
    private int res = Integer.MAX_VALUE;
    private TreeNode pre;
    public int getMinimumDifference(TreeNode root) {
        if(root == null) return 0;
        traversal(root);
        return res;
    }
    private void traversal(TreeNode node){
        if(node == null) return;
        traversal(node.left);
        if(pre != null) res = Math.min(res, node.val - pre.val);
        pre = node;
        traversal(node.right);
    }
}
//中序迭代
class Solution {
    public int getMinimumDifference(TreeNode root) {
        if(root == null) return 0;
        Deque<TreeNode> deque = new LinkedList<>();
        int res = Integer.MAX_VALUE;
        TreeNode pre = null;
        deque.push(root);
        while(!deque.isEmpty()){
            TreeNode cur = deque.pop();
            if(cur != null){
                if(cur.right != null) deque.push(cur.right);
                deque.push(cur);
                deque.push(null);
                if(cur.left != null) deque.push(cur.left);
            }
            else{
                TreeNode temp = deque.pop();
                if(pre != null) res = Math.min(res, temp.val - pre.val);
                pre = temp;
            }
        }
        return res;
    }
}

501.二叉搜索树中的众数

力扣题目链接

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

解答：

class Solution {
    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        if(root == null) return list.stream().mapToInt(Integer::intValue).toArray();;

        searchBST(root, map);
        List<Map.Entry<Integer, Integer>> maplist = map.entrySet().stream()
            .sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
            .collect(Collectors.toList());
        list.add(maplist.get(0).getKey());
        for(int i = 1; i < maplist.size(); i++){
            if(maplist.get(i).getValue() == maplist.get(i - 1).getValue()){
                list.add(maplist.get(i).getKey());
            } else {
                break;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    private void searchBST(TreeNode node, Map<Integer, Integer> map){
        if(node == null) return;
        TreeNode cur = node;
        map.put(cur.val, map.getOrDefault(cur.val, 0) + 1);
        searchBST(cur.left, map);
        searchBST(cur.right, map);
    }
}
//优化
class Solution {
    int count;
    int max_count;
    TreeNode pre;
    List<Integer> resList = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        count = 0;
        max_count = 0;
        findMode1(root);
        int[] res = new int[resList.size()];
        for(int i = 0; i < resList.size(); i++){
            res[i] = resList.get(i);
        }
        return res;
    }
    private void findMode1(TreeNode node){
        if(node == null) return;
        findMode1(node.left);

        if(pre == null || node.val == pre.val){
            count++;
        } else {
            count = 1;
        }
        if(count > max_count){
            resList.clear();
            max_count = count;
            resList.add(node.val);
        } else if(count == max_count) {
            resList.add(node.val);
        }

        pre = node;
        findMode1(node.right);
    }
}

236. 二叉树的最近公共祖先

力扣题目链接

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

解答：

//递归，终止条件是找到p或者q
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == q || root == p) return root;
        TreeNode res = root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null){
            return right;
        } else if(right == null){
            return left;
        } else {
            return root;
        }

    }
}
//迭代
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == q || root == p) return root;
        int max = Integer.MAX_VALUE;
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode cur = root, pre = null;
        while(cur != null || !deque.isEmpty()){
            while(cur != null){
                deque.push(cur);
                cur = cur.left;
            }// 子树的最左边的节点
            cur = deque.pop();
            if(cur.right == null || cur.right == pre){
                if(cur == p || cur == q){
                    if((cur.left != null && cur.left.val == max) || (cur.right != null && cur.right.val == max)) return cur;
                    cur.val = max;
                }

                // p/q是 左/右 , 返回中
                if(cur.left != null && cur.left.val == max && cur.right != null && cur.right.val == max) return cur;

                // MAX_VALUE 往上传递
                if((cur.left != null && cur.left.val == max) || (cur.right != null && cur.right.val == max)) cur.val = max;
                pre = cur;
                cur = null;
            }
            else{//存在右二叉树没有遍历
                deque.push(cur);
                cur = cur.right;
            }
        }
        return null;
    }
}

235. 二叉搜索树的最近公共祖先

力扣题目链接

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

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

解答：

//递归
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == q || root == p) return root;

        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        } else if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return root;
        }

    }
}

701.二叉搜索树中的插入操作

力扣题目链接

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

解答：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null || root.val == val) return new TreeNode(val);
        if(root.val > val) root.left = insertIntoBST(root.left, val);
        else root.right = insertIntoBST(root.right, val);
        return root;
    }
}

450.删除二叉搜索树中的节点

力扣题目链接

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

解答：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return root;
        if(root.val == key){
            TreeNode left = root.left;
            if(root.right != null){
                TreeNode right = root.right;
                root = root.right;
                while(root.left != null) root = root.left;
                root.left = left;
                left = right;
            }
            return left;
        }
        if(root.val > key) root.left = deleteNode(root.left, key);
        if(root.val < key) root.right = deleteNode(root.right, key);
        return root;
    }
}

669. 修剪二叉搜索树

力扣题目链接

给定一个二叉搜索树，同时给定最小边界 L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

解答：

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        if(root.val < low) root = root.right;
        else if(root.val > high) root = root.left;

        return root;
    }
}

108.将有序数组转换为二叉搜索树

力扣题目链接

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

解答：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length-1);
        return root;
    }
    private TreeNode traversal(int[] nums, int left, int right){
        if(left > right) return null;
        int mid1 = (right + left) / 2;
        TreeNode node = new TreeNode(nums[mid1]);
        node.left = traversal(nums, left, mid1-1);
        node.right = traversal(nums, mid1+1, right);
        return node;
    }
}

538.把二叉搜索树转换为累加树

力扣题目链接

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

解答：

//递归1
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;
        root.right = convertBST(root.right);

        TreeNode node = root.right;
        if(node != null){
            while(node.left != null) node = node.left;
            root.val += node.val;
        }

        node = root.left;
        if(node != null){
            while(node.right != null) node = node.right;
            node.val += root.val;
        }
        root.left = convertBST(root.left);
        return root;
    }
}

//递归2
class Solution {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        convertBST1(root);
        return root;
    }
    private void convertBST1(TreeNode node){
        if(node == null) return;
        convertBST1(node.right);
        node.val += sum;
        sum = node.val;
        convertBST1(node.left);
    }
}

总结

二叉树分类：

• 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
• 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
• 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

注意在普通二叉树的属性中，一般为后序，例如单纯求深度就用前序，二叉树：找所有路径 也用了前序，这是为了方便让父节点指向子节点。

所以求普通二叉树的属性还是要具体问题具体分析。

二叉树专题汇聚为一张图：

其他

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

解答：

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int sum){
        if(node == null) return 0;
        int cur = node.val + sum * 10;

        if(node.left == null && node.right == null) return cur;

        int left = dfs(node.left, cur);
        int right = dfs(node.right, cur);
        return left + right;
    }
}

1382.将二叉搜索树变平衡

力扣题目链接

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

如果有多种构造方法，请你返回任意一种。

解答：

import java.util.*;

class Solution {
    List<Integer> list = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        if(root == null) return  root;
        inorder(root);

        return getTree(root, 0, list.size() - 1);
    }

    private void inorder(TreeNode node) { // 对二叉树进行中序遍历
        if (node == null) return;
        inorder(node.left);
        list.add(node.val);
        inorder(node.right);
    }

    private TreeNode getTree(TreeNode root, int left, int right){  // 根据中序遍历结果重建二叉树
        if(left > right) return null;
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = getTree(root, left, mid - 1);
        node.right = getTree(root, mid + 1, right);
        return node;
    }
}

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

解答:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if root is None:
            return 0
        res = 0
        def dfs(node: Optional[TreeNode]) -> int: # 返回最大深度
            if node is None:
                return -1
            left = dfs(node.left) + 1
            right = dfs(node.right) + 1
            nonlocal res # 声明 res 为非局部变量
            res = max(res, left+right)
            return max(left, right)

        dfs(root)
        return res

230. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

解答:

中序遍历:时间复杂度:$O(n)$

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        res = 0
        def dfs(root: Optional[TreeNode]) -> None:
            nonlocal res, k
            if root is None or k == 0:
                return

            dfs(root.left)
            k -= 1
            if k == 0:
                res = root.val
            dfs(root.right)
        dfs(root)
        return res

我的思路:时间复杂度$O(n\log k)$

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;
    }
}

class Solution {
    Queue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    public int kthSmallest(TreeNode root, int k) {
        if(pq.size() < k){
            pq.offer(root.val);
        } else if(pq.peek() > root.val){
            pq.poll();
            pq.offer(root.val);
        }
        if(root.left != null){
            kthSmallest(root.left,k);
        }
        if(root.right != null){
            kthSmallest(root.right,k);
        }
        return pq.peek();
    }
}

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null
• 展开后的单链表应该与二叉树 先序遍历 顺序相同

解答:

MyCode:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def findRight(self, root: Optional[TreeNode]) -> TreeNode:
        if root is None or root.right is None:
            return root
        return self.findRight(root.right)
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root is None or (root.left is None and root.right is None):
            return root

        def dfs(root: Optional[TreeNode]) -> None:
            if root is None:
                return None
            dfs(root.right)
            dfs(root.left)
            if root.left:
                temp = root.right
                root.right = root.left
                root.left = None
                self.findRight(root).right = temp

        dfs(root)

上述的简化(分治)时间复杂度：$O(n)$

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        """
        Do not return anything, modify root in-place instead.
        """        
        if root is None:
            return None
        left_tail = self.flatten(root.left)
        right_tail = self.flatten(root.right)

        if left_tail:
            left_tail.right = root.right
            root.right = root.left
            root.left = None
        return right_tail or left_tail or root

头插法时间复杂度：$O(n)$

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    head = None # 当前头节点
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """        
        if root is None:
            return None
        self.flatten(root.right)
        self.flatten(root.left)

        root.left = None
        root.right = self.head # 将当前节点放到头节点之上
        self.head = root # 更新头节点

437. 路径总和 III

解答:

特殊情况:560. 和为 K 的子数组

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    targetSum1 = 0
    cnt = 0
    def dfs(self, node: Optional[TreeNode], pre_sum: defaultdict, sum: int) -> None:
        if node is None:
            return
        sum += node.val

        self.cnt += pre_sum[sum-self.targetSum1] # 把 node 当作路径的终点，统计有多少个起点
        pre_sum[sum] += 1
        self.dfs(node.left, pre_sum, sum)
        self.dfs(node.right, pre_sum, sum)
        pre_sum[sum] -= 1 # 恢复现场

    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        pre_sum = defaultdict(int)
        pre_sum[0] = 1
        self.targetSum1 = targetSum
        self.dfs(root, pre_sum, 0)

        return self.cnt

124. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = -inf

        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            max_left = dfs(node.left)
            max_right = dfs(node.right)
            nonlocal res

            res = max(res, max_left+max_right+node.val) 
            return max(max(max_left, max_right) + node.val, 0) #若该节点下的路径和小于零,则放弃该节点;大于零则返回最大路径,这样保证了dfs返回值大于零

        dfs(root)
        return res

208. 实现 Trie (前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

解答:

二叉树变成26叉树

class Node:
    __slots__ = 'son', 'end'

    def __init__(self) -> None:
        self.son = {}
        self.end = None

class Trie:

    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.son:
                cur.son[c] = Node() # 无路可走就造陆
            cur = cur.son[c]
        cur.end = True

    def find(self, word: str) -> int:
        cur = self.root
        for c in word:
            if c in cur.son:
                cur = cur.son[c]
            else: # 道不同，不相为谋
                return 0
        return 1 if cur.end else 2 # 终点不同

    def search(self, word: str) -> bool:
        return self.find(word) == 1

    def startsWith(self, prefix: str) -> bool:
        return self.find(word=prefix) != 0