【算法】二叉树

g0dam

2024-10-29

Algorithm

二叉树

二叉树理论基础篇

二叉树的种类

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。也可以说深度为k，有2^k-1个节点的二叉树。

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

二叉搜索树：前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_set底层实现是哈希表。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。
那么链式存储方式就用指针，顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

顺序存储

用数组来存储二叉树如何遍历的呢？如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

二叉树的遍历方式

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
广度优先遍历：一层一层的去遍历。
- 层次遍历（迭代法）
  这两种遍历是图论中最基本的两种遍历方式，后面在介绍图论的时候还会介绍到。
  我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。
  之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
  而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

二叉树的递归遍历：

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

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

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

二叉树的迭代遍历：我们在栈与队列：匹配问题都是栈的强项 (opens new window)中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
前序遍历（迭代法）:前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

二叉树的统一迭代法:我们以中序遍历为例，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。这种方法也可以叫做标记法。

// 迭代法前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

// 迭代法中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}

// 迭代法后序遍历代码
class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）         
                               
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
   }
}

二叉树的结构

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

二叉树的层序遍历

102.二叉树的层序遍历

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

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

/**
 * Definition for a binary tree node.
 * 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 {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        // checkFun01(root, 0)
        checkFun02(root);
        return resList;
    }

//BFS 递归方式
    public void checkFun01(TreeNode node, Integer deep){
        if(node == null) return;
        deep++;

        if(resList.size() < deep){
            // 当层级增加时，List的Item也增加，利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);
        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    // 迭代方式 - 借助队列
    public void checkFun02(TreeNode node){
        if(node == null) return ;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while(!que.isEmpty()){
            List<Integer> itemList = new LinkedList<Integer>();
            int len = que.size();

            while(len > 0){
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if(tmpNode.left != null) que.offer(tmpNode.left);
                if(tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }
    }
}

107.二叉树的层次遍历 II

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

相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。

199.二叉树的右视图

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

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if(root == null){
            return list;
        }

        que.offerLast(root);
        while(!que.isEmpty()){
            int levelSize = que.size();

            for(int i = 0; i < levelSize; i++){
                TreeNode poll = que.pollFirst();

                if(poll.left != null){
                    que.addLast(poll.left);
                }
                if(poll.right != null){
                    que.addLast(poll.right);
                }
                if(i == levelSize - 1){
                    list.add(poll.val);
                }
            }
        }
        return list;
    }
}

637.二叉树的层平均值

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

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if(root == null){
            return list;
        }

        que.offerLast(root);
        while(!que.isEmpty()){
            int levelSize = que.size();
            Double levelSum = 0.0;
            for(int i=0; i < levelSize; i++){
                TreeNode poll = que.pollFirst();

                levelSum += poll.val;

                if(poll.left != null){
                    que.addLast(poll.left);
                }
                if(poll.right != null){
                    que.addLast(poll.right);
                }
            }
            list.add(levelSum / levelSize);
        }
        return list;
    }
}

429.N叉树的层序遍历

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

返回其层序遍历:
[ [1], [3,2,4], [5,6] ]

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<Node> que = new LinkedList<>();

        if(root == null){
            return list;
        }

        que.offerLast(root);
        while(!que.isEmpty()){
            int levelSize = que.size();
            List<Integer> levelList = new ArrayList<>();

            for(int i = 0; i < levelSize; i++){
                Node poll = que.pollFirst();

                levelList.add(poll.val);

                List<Node> children = poll.children;
                if(children == null || children.size() == 0){
                    continue;
                }
                for(Node child : children){
                    if (child != null){
                        que.offerLast(child);
                    }
                }
            }
            list.add(levelList);
        }
        return list;
    }
}

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

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
        List<Integer> result = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int max = Integer.MIN_VALUE;
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                max = Math.max(max, node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            result.add(max);
        }
        return result;
    }
}

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

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

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

class Solution {
    public Node connect(Node root) {
        Queue<Node> tmpQueue = new LinkedList<Node>();
        if(root != null) tmpQueue.add(root);

        while(tmpQueue.size() != 0){
            int size = tmpQueue.size();
            Node cur = tmpQueue.poll();
            if(cur.left != null) tmpQueue.add(cur.left);
            if(cur.right != null) tmpQueue.add(cur.right);

            for(int index = 1; index < size; index++){
                Node next = tmpQueue.poll();
                if(next.left != null) tmpQueue.add(next.left);
                if(next.right != null) tmpQueue.add(next.right);

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

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

给定一个二叉树：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

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

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if(root != null){
            queue.add(root);
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            Node node = null;
            Node nodePre = null;

            for(int i = 0; i < size; i++){
                if(i == 0){
                    nodePre = queue.poll(); //取出本层头一个节点
                    node = nodePre;
                }else{
                    node = queue.poll();
                    nodePre.next = node; // 本层前一个节点 next 指向当前节点
                    nodePre = nodePre.next;
                }
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            nodePre.next = null ; // 本层最后一个next指向null
        }
        return root;
    }
}

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。
在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

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

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int size  = queue.size();
            depth++;
            TreeNode cur = null;
            for(int i = 0; i < size; i++){
                cur = queue.poll();
                if(cur.left == null && cur.right == null){
                    return depth;
                }
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
        }
        return depth;
    }
}

// 递归法
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        // 在计算最小深度时，当一个子树为空时，必须沿着另一个非空子树去寻找叶子节点，因为只有到叶子节点的路径才算作深度路径。
        if(root.left == null) return rightDepth + 1;
        if(root.right == null) return leftDepth + 1;

        return Math.min(leftDepth, rightDepth) + 1;
    }
}

class Solution {
    int depth = 0;
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        dep(root);
        return minDepth == Integer.MAX_VALUE ? 0 : minDepth;
    }

    void dep(TreeNode root){
        if(root == null) return ;
        depth++;
        dep(root.left);
        dep(root.right);
        if(root.left == null && root.right == null)
            minDepth = Math.min(minDepth, depth);
        depth--;
    }
}

Queue<TreeNode> queue = new LinkedList<>(); 用 Queue 来声明变量，但使用 LinkedList 来实例化它。这种方式在 Java 中是允许的，而且有它的设计意义。

接口与实现分离
- Queue 是 Java 中的一个接口（interface），它定义了队列（FIFO，先进先出）的行为规范，比如 offer、poll、peek 等方法。
- LinkedList 是一个具体的类，它实现了 Queue 接口，所以 LinkedList 可以被用来作为 Queue 的实现。
- 使用接口来声明变量（即 Queue<TreeNode> queue），可以让代码更加灵活。如果你想要更换为不同的队列实现（例如 PriorityQueue），可以直接替换而不改变其他代码。这是面向接口编程的一个基本原则。
LinkedList 作为 Queue 的实现
- LinkedList 是 Java 中一个双向链表的实现，同时也实现了多个接口，包括 Queue 和 Deque。
- 在 Queue<TreeNode> queue = new LinkedList<>(); 中，声明的是 Queue 类型，但它的实际运行时类型是 LinkedList，因此可以调用 Queue 接口中的方法如 offer 和 poll，它们在 LinkedList 中都有具体的实现。
为什么这样做？
- 通过 Queue 来声明变量，使得代码的依赖性降低。换句话说，代码只依赖于 Queue 的行为（方法），而不关心它的具体实现。
- 这种方式不仅提高了代码的可读性和可维护性，也使得在需要时更容易替换底层的实现类。

代码示例
如果以后想替换实现，只需更改实例化部分即可：

1	Queue<TreeNode> queue = new PriorityQueue<>(); // 假设需要优先队列

226.翻转二叉树

翻转一棵二叉树。

https://www.programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E6%80%9D%E8%B7%AF

递归的中序遍历是不行的，因为使用递归的中序遍历，某些节点的左右孩子会翻转两次。
如果非要使用递归中序的方式写，也可以，如下代码就可以避免节点左右孩子翻转两次的情况：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};

代码虽然可以，但这毕竟不是真正的递归中序遍历了。但使用迭代方式统一写法的中序是可以的。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                st.push(node);                          // 中
                st.push(NULL);
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

假设我们有如下二叉树：

这棵树的目标是要翻转每个节点的左右子树。翻转后应该变成：

接下来，我们按照代码的执行逻辑一步一步地展示栈的变化过程。

初始状态

栈初始化并将根节点 1 压入栈中。

1	Stack: [1]

第一步：处理节点 1

弹出节点 1，因为它不为空，按照右-中-左顺序进行压栈。
- 将 1 的右子节点 3 压入栈。
- 将节点 1 本身压入栈。
- 压入 NULL 标记。
- 将 1 的左子节点 2 压入栈。

1	Stack: [3, 1, NULL, 2]

第二步：处理节点 2

弹出节点 2，因为它不为空，按照右-中-左顺序进行压栈。
- 将 2 的右子节点 5 压入栈。
- 将节点 2 本身压入栈。
- 压入 NULL 标记。
- 将 2 的左子节点 4 压入栈。

1	Stack: [3, 1, NULL, 5, 2, NULL, 4]

第三步：处理节点 4

弹出节点 4，它没有子节点。
- 将节点 4 本身压入栈。
- 压入 NULL 标记。

1	Stack: [3, 1, NULL, 5, 2, NULL, 4, NULL]

第四步：处理空标记（处理节点 4）

遇到 NULL 标记，弹出 NULL 并获取节点 4。
对 4 进行翻转，但 4 没有子节点，结构保持不变。

1	Stack: [3, 1, NULL, 5, 2, NULL]

第五步：处理节点 5

弹出节点 5，它没有子节点。
- 将节点 5 本身压入栈。
- 压入 NULL 标记。

1	Stack: [3, 1, NULL, 5, NULL]

第六步：处理空标记（处理节点 5）

遇到 NULL 标记，弹出 NULL 并获取节点 5。
对 5 进行翻转，但 5 没有子节点，结构保持不变。

1	Stack: [3, 1, NULL]

第七步：处理空标记（处理节点 2）

遇到 NULL 标记，弹出 NULL 并获取节点 2。
对 2 进行翻转，使得 5 成为左子节点，4 成为右子节点。

1	Stack: [3]

第八步：处理节点 3

弹出节点 3，它没有子节点。
- 将节点 3 本身压入栈。
- 压入 NULL 标记。

1	Stack: [3, NULL]

第九步：处理空标记（处理节点 3）

遇到 NULL 标记，弹出 NULL 并获取节点 3。
对 3 进行翻转，但 3 没有子节点，结构保持不变。

Stack: []

第十步：处理空标记（处理节点 1）

遇到 NULL 标记，弹出 NULL 并获取节点 1。
对 1 进行翻转，使得 3 成为左子节点，2 成为右子节点。

最终结构

现在树已完全翻转，得到的树结构如下：

这样通过一步步地栈操作，我们成功地翻转了这棵二叉树。每次遇到 NULL 标记时，栈顶的节点都可以安全地进行左右子节点的交换，直到栈为空。

 // DFS递归
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        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;
    }
}

 // BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            int size = deque.size();
            while(size-- > 0){
                TreeNode node = deque.poll();
                swap(node);
                if(node.left != null) deque.offer(node.left);
                if(node.right != null) deque.offer(node.right);
            }
        }
        return root;
    }

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

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

在二叉树的遍历中，前序遍历和后序遍历有不同的应用场景，特别是在计算树的深度和高度时：

拓展

1. 深度（Depth）与前序遍历

前序遍历（中左右）的顺序意味着我们从根节点开始逐层深入，这与深度的定义相契合。
在递归实现中，我们在每个节点递归进入其子节点时，都可以累计当前的深度值。
因此，前序遍历常用于计算深度，即从根节点到叶节点的最长路径。
例如，在遍历中不断向下递归时，我们能够计算并更新树的最大深度或是找到二叉树的最小深度。

2. 高度（Height）与后序遍历

后序遍历（左右中）的顺序则是从子节点回溯到父节点。
在计算高度时，这种遍历顺序最为合理，因为树的高度定义为“节点到叶节点最长路径的长度”，而要计算高度，就需要先知道子节点的高度，然后取左右子树的最大高度，再加 1。
例如，当递归返回到父节点时，可以利用左右子树的高度来计算当前节点的高度。因此，后序遍历可以很好地用于计算树的高度。

简单示例

假设我们有这样一棵二叉树：

用前序遍历计算深度

我们从根节点 1 出发，逐步递归到每一层的叶节点，在每次进入下一层时更新当前深度。
比如这棵树的最大深度是 3（从根节点 1 到叶节点 4 或 5）。

用后序遍历计算高度

在后序遍历中，首先递归到叶节点 4 和 5，然后回溯到节点 2，可以计算出 4 和 5 的高度，然后得出节点 2 的高度，再回溯到根节点。
最终树的高度也是 3，因为从叶节点 4 或 5 到根节点 1 的最长路径长度为 3。

根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

解题

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

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

使用递归

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

class Solution {
    int maxnum = 0;
    public int maxDepth(TreeNode root) {
        ans(root, 0);
        return maxnum;
    }

    void ans(TreeNode tr, int tmp){
        if(tr == null) return;
        tmp++;
        maxnum = maxnum < tmp ? tmp : maxnum;
        ans(tr.left, tmp);
        ans(tr.right, tmp);
        tmp--;
    }
}

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

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

题解

递归解法

确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。
确定终止条件：如果为空节点的话，就返回0，表示节点数为0。

确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一（加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。

class Solution {
private:
    int getNodesNum(TreeNode* cur) {
        if (cur == NULL) return 0;
        int leftNum = getNodesNum(cur->left);      // 左
        int rightNum = getNodesNum(cur->right);    // 右
        int treeNum = leftNum + rightNum + 1;      // 中
        return treeNum;
    }
public:
    int countNodes(TreeNode* root) {
        return getNodesNum(root);
    }
};

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

迭代解法

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                result++;   // 记录节点数量
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

完全二叉树思路解题

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。

class Solution {
    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;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

110.平衡二叉树

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

下面的不是了

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

下面主要讲解下用层序遍历来求高度的思路：
假设有一棵二叉树：

最大深度是 3，因为从根节点 1 到叶子节点 4 或 5 的路径长度是 3。
高度在叶子节点 4 和 5 为 0，节点 2 的高度为 1，根节点 1 的高度为 2。

层序遍历适合求最大深度。每遍历一层，深度加一。对于上面这棵树，层序遍历步骤如下：

第一层：根节点 1，深度为 1。
第二层：节点 2 和 3，深度为 2。
第三层：节点 4 和 5，深度为 3。

层序遍历到叶子节点时，最大深度为 3。

后序遍历求高度，我们需要从叶子节点开始逐层向上计算。可以使用栈来模拟后序遍历，通过递归的方式来求每个节点的高度：

访问叶子节点 4 和 5，高度为 0。
回溯到节点 2：2 的高度是 max(4 的高度, 5 的高度) + 1 = 1。
访问节点 3，高度为 0。
回溯到根节点 1：1 的高度是 max(2 的高度, 3 的高度) + 1 = 2。

最终，根节点的高度为 2，这也是整个树的高度。

class Solution {
    // 递归法
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if(leftHeight == -1){
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if(rightHeight == -1){
            return -1;
        }
        // 左右子树高度差大于1就不是平衡树了
        if(Math.adb(leftHeight, - rightHeight) > 1){
            return -1;
        }
        return Math.max(leftHeight, rightHeight);
    }
}

class Solution {
    /**
     * 迭代法，效率较低，计算高度时会重复遍历
     * 时间复杂度：O(n^2)
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode inNode = stack.peek();
            // 右节点为null或已遍历过
            if(inNode.right == null || inNode.right == pre){
                // 比较左右子树高度差，输出
                if(Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1){
                    return false;
                }
                stack.pop();
                pre = inNode;
                root = null;
            }else{
                root = inNode.right;
            }
        }
        return true;
    }

    /**
     * 层序遍历，求结点的高度
     */
     public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while(!deque.isEmpty()){
            int size = deque.size();
            depth++;
            for(int i= 0; i < size; i++){
                TreeNode poll = deque.poll();
                if(poll.left != null){
                    deque.offer(poll.left);
                }
                if(poll.right != null){
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
     }
}

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        List<Integer> paths = new ArrayList<>();
        traversal(root, paths, res);
        return res;
    }

    private void traversal(TreeNode root, List<Integer> paths, List<String> res){
        paths.add(root.val); // 前序遍历
        // 遇到叶子结点
        if(root.left == null && root.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(root.left != null){
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);
        }
        if(root.right != null){
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);
        }
    }
}

class Solution {
    List<String> result = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        deal(root, "");
        return result;
    }

    public void deal(TreeNode node, String s){
        if(node == null) return;
        if(node.left == null && node.right == null){
            result.add(new StringBuilder(s).append(node.val).toString());
            return;
        }
        String tmp = new StringBuilder(s).append(node.val).append("->").toString();
        deal(node.left, tmp);
        deal(node.right, tmp);
    }
}

404.左叶子之和

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

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        int leftValue = sumOfLeftLeaves(root.left);
        int rightValue = sumOfLeftLeaves(root.right);

        int midValue = 0;
        if(root.left != null && root.left.left == null && root.left.right == null){
            midValue = root.left.val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
}

// 迭代法
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        int result = 0;
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left != null && node.left.left ==null && node.left.right == null){
                result += node.left.val;
            }
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
        }
        return result;
    }
}

513.找树左下角的值

给定一个二叉树的根节点 root，请找出该二叉树的最底层最左边节点的值。
这张图是7

递归法求解时要同时记录深度，使用层次遍历更为方便

// 递归法
class Solution {
    private int Deep = -1;
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root, 0);
        return value;
    }

    private void findLeftValue(TreeNode root, int deep){
        if(root == null) return;
        if(root.left == null && root.right == null){
            if(deep > Deep){
                value = root.val;
                Deep = deep;
            }
        }
        if(root.left != null) findLeftValue(root.left, deep+1);
        if(root.right != null) findLeftValue(root.right, deep+1);
    }
}

// 迭代法
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode poll = queue.poll();
                if(i == 0){
                    res = poll.val;
                }
                if(poll.left != null){
                    queue.offer(poll.left);
                }
                if(poll.right != null){
                    queue.offer(poll.right);
                }
            }
        }
        return res;
    }
}

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        targetSum -= root.val;
        // 叶子结点
        if(root.left == null && root.right == null){
            return targetSum == 0;
        }
        if(root.left != null){
            boolean left = hasPathSum(root.left, targetSum);
            if(left) return true;
        }
        if(root.right != null){
            boolean right = hasPathSum(root.right, targetSum);
            if(right) return true;
        }
        return false;
    }
}

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        if(root != null)
            stack.add(root);
        while(!stack.isEmpty()){
            TreeNode curr = stack.peek();
            if(curr != null){
                stack.pop();
                if(curr.right != null){
                    stack.add(curr.right);
                }
                stack.add(curr);
                stack.add(null);
                if(curr.left != null)
                    stack.add(curr.left);
            } else{
                stack.pop();
                TreeNode temp = stack.pop();
                if(pre != null && pre.val >= temp.val)
                    return false;
                pre = temp;
            }
        }
        return true;
    }
}

// 递归法
class Solution {
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        if(!left){return false;}
        // 中
        if(max != null && root.val <= max.val){
            return false;
        }
        max = root;
        // 右
        boolean right = isValidBST(root.right);
        return right;
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper){
        if(node == null){
            return true;
        }
        if(node.val <= lower || node.val >= upper){
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}

501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按任意顺序返回。

假定 BST 满足如下定义：

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

class Solution {
    ArrayList<Integer> resList;
    int maxCount;
    int count;
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        findMode1(root);
        int[] res = new int[resList.size()];
        for(int i = 0; i < resList.size(); i++){
            res[i] = resList.get(i);
        }
        return res;
    }

    public void findMode1(TreeNode root){
        if(root == null){
            return;
        }
        findMode1(root.left);
        int rootValue = root.val;
        // 计数
        if(pre == null || rootValue != pre.val){
            count = 1;
        }else{
            count++;
        }
        // 更新结果及maxCount
        if(count > maxCount){
            resList.clear();
            resList.add(rootValue);
            maxCount = count;
        }else if (count == maxCount){
            resList.add(rootValue);
        }
        pre = root;
        findMode1(root.right);
    }
}

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

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

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

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

        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null && right == null){
            return null;
        }else if(left == null && right != null){
            return right;
        }else if(left != null && right == null){
            return left;
        }else{
            return root;
        }
    }
}

迭代法解决

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int max = Integer.MAX_VALUE;
        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root, pre = null;
        while(cur != null || !st.isEmpty()){
            while(cur != null){
                st.push(cur);
                cur = cur.left;
            }
            cur = st.pop();
            if(cur.right == null || cur.right == pre){
                // p/q是 中/左 或者 中/右 , 返回中
                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 {
                st.push(cur);
                cur = cur.right;
            }
        }
        return null;
    }
}