当前位置：首页 > article >正文

代码随想录_二叉树

article 2025/2/11 12:34:20

二叉树

二叉树的递归遍历

144.二叉树的前序遍历
145.二叉树的后序遍历
94.二叉树的中序遍历

// 前序遍历·递归·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);            
    }
}

589. N 叉树的前序遍历

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        fun(root,res);
        return res;
    }

    public void fun(Node cur,List<Integer> res) {
        if(cur == null) return;// basecase

        res.add(cur.val);// 根
        for(Node node : cur.children) {// 孩子
            fun(node,res);
        }

        return;// 结束
    }

}

590. N 叉树的后序遍历

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        fun(root,ans);
        return ans;
    }

    public void fun(Node cur,List<Integer> ans) {
        if(cur == null) return;

        for(Node node : cur.children) {// 孩子
            fun(node,ans);
        }

        ans.add(cur.val);// 根
        return;
    }
}

二叉树的迭代遍历

前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        // 1. 剪枝
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;
        // 2. 定义容器
        Stack<TreeNode> stack = new Stack<>();
        // 3. 遍历
        stack.push(root);
        while(!stack.isEmpty()) {
            // 中
            // 不用判断cur是否为null, 走到这里root != null, 且root为null的孩子不会被放入栈中
            TreeNode cur = stack.pop();
            ans.add(cur.val);
            // 右
            if(cur.right != null) {
                stack.push(cur.right);
            }
            // 左
            if(cur.left != null) {
                stack.push(cur.left);
            }
        }
        // 4. 返回
        return ans;
    }
}

后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        // 1. 特殊处理
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;
        // 2. 定义容器
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        // 3. 遍历
        while(!stack.isEmpty()) {
            // 中
            TreeNode cur = stack.pop();
            ans.add(cur.val);
            // 左
            if(cur.left != null) {
                stack.push(cur.left);
            }
            // 右
            if(cur.right != null) {
                stack.push(cur.right);
            }
        }
        // 4. 返回(翻转原集合)
        Collections.reverse(ans);
        return ans;
    }
}

中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 1. 定义容器, 特殊判断
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;

        Stack<TreeNode> stack = new Stack<>(); 
        // 2. 循环遍历
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()) {
            if(cur != null) {
                // 左
                stack.push(cur);
                cur = cur.left;
            }else {
                // 中
                cur = stack.pop();
                ans.add(cur.val);
                // 右
                cur = cur.right;
            }
        }
        // 3. 返回
        return ans;
    }
}

注: while(cur != null || !stack.isEmpty())
要统一push, 在while里push

如果只有!stack.isEmpty(), 那一开始栈空, 不会进入循环, 且由于进入栈中的不一定是要处理的元素, 可能出现pop后栈空了, 但是cur右孩子还能进栈的情况

102.二叉树的层序遍历

102. 二叉树的层序遍历

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

思路: 队列, 记录每层的结点数, 每次循环完该层的所有节点, 将该层结点的list存入ans中

代码:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 1. 定义容器, 返回的list, queue
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        // 2. 对root进行处理
        if(root != null) q.offer(root);

        // 3. 开始遍历
        while(!q.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = q.size();

            while(size-- > 0) {
                TreeNode cur = q.poll();
                list.add(cur.val);

                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }

            ans.add(list);
        }

        // 4. 返回
        return ans;
    }
}

107.二叉树的层序遍历 II

107. 二叉树的层序遍历 II

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

思路: 在102的基础上对ans数组进行反转

代码:

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()) {
            int size = q.size();
            List<Integer> list = new ArrayList<>();
            while(size-- > 0) {
                TreeNode cur = q.poll();
                list.add(cur.val);
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
            ans.add(list);
        }
        // 反转
        Collections.reverse(ans);
        return ans;
    }
}

199.二叉树的右视图

199. 二叉树的右视图

思路: 在层次遍历的中, 对收集的条件进行更改

代码:

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 1. 定义容器, 返回的list, queue
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        // 2. 对root进行处理
        if(root != null) q.offer(root);

        // 3. 开始遍历
        while(!q.isEmpty()) {
            int size = q.size();
            while(size-- > 0) {
                TreeNode cur = q.poll();
                // 当size-- == 1 , size == 0, 遍历到该层的最后一个结点
                if(size == 0) {
                    ans.add(cur.val);
                }
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
        }

        // 4. 返回
        return ans;
    }
}

637.二叉树的层平均值

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

思路: 定义一个double类型的sum, 使用for循环对每层进行遍历(size大小不能改变, 最后要用sum/size)

代码:

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        // 1. 定义容器, 返回的list, queue
        List<Double> ans = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        // 2. 对root进行处理
        if(root != null) q.offer(root);

        // 3. 开始遍历
        while(!q.isEmpty()) {
            int size = q.size();
            double sum = 0;

            for(int i = 0;i < size;i++) {
                TreeNode cur = q.poll();
                sum += cur.val;
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }

            ans.add(sum / size);
        }

        // 4. 返回
        return ans;
    }
}

429.N 叉树的层序遍历

429. N 叉树的层序遍历

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

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

思路: 遍历同层每个节点的同时, 收集children中的子节点

代码:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        // 1. 定义容器, 返回的list, queue
        List<List<Integer>> ans = new ArrayList<>();
        Queue<Node> q = new LinkedList<>();

        // 2. 对root进行处理
        if(root != null) q.offer(root);

        // 3. 开始遍历
        while(!q.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = q.size();

            while(size-- > 0) {
                Node cur = q.poll();
                list.add(cur.val);

                List<Node> c = cur.children;
                for(int i = 0;i < c.size();i++) {
                    q.offer(c.get(i));
                }
            }

            ans.add(list);
        }

        // 4. 返回
        return ans;
    }
}

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

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

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        // 1. 定义容器, 返回的list, queue
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        // 2. 对root进行处理
        if(root != null) q.offer(root);

        // 3. 开始遍历
        while(!q.isEmpty()) {
            int size = q.size();
            int maxV = Integer.MIN_VALUE;

            while(size-- > 0) {
                TreeNode cur = q.poll();
                maxV = maxV >= cur.val ? maxV : cur.val;

                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }

            ans.add(maxV);
        }

        // 4. 返回
        return ans;
    }
}

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

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> q = new LinkedList<>();
        if(root != null) q.offer(root);

        while(!q.isEmpty()) {
            int size = q.size();
            Node cur = q.poll();
            if(cur.left != null) q.offer(cur.left);
            if(cur.right != null) q.offer(cur.right);

            for(int i = 1;i < size;i++) {
                Node next = q.poll();
                if(next.left != null) q.offer(next.left);
                if(next.right != null) q.offer(next.right);

                cur.next = next;
                cur = next;
            }
        }

        return root;
    }
}

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

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

同116

104.二叉树的最大深度

104. 二叉树的最大深度

法一：迭代法

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

法二：层次遍历

class Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        int depth = 0;

        while(!q.isEmpty()) {
            int size = q.size();
            depth++;
            for(int i = 0;i < size;i++) {
                TreeNode cur = q.poll();
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
        }

        return depth;
    }
}

111.二叉树的最小深度

111. 二叉树的最小深度

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

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

输入：root = [3,9,20,null,null,15,7]
输出：2

注：某节点的左右孩子均为null时，该节点所在的层次就是最小深度

**法一：**迭代法

代码：

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;

        int leftDepth = Integer.MAX_VALUE;
        int rightDepth = Integer.MAX_VALUE;

        if(root.left != null){
            leftDepth = minDepth(root.left);
        }
        if(root.right != null){
            rightDepth = minDepth(root.right);
        }

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

**法二：**层次遍历

代码：

class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        int depth = 0;

        while(!q.isEmpty()) {
            int size = q.size();
            depth++;
            for(int i = 0;i < size;i++) {
                TreeNode cur = q.poll();
                if(cur.left == null && cur.right == null) return depth;
                
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
        }

        return depth;
    }
}

226.翻转二叉树

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

**法一：**迭代法（前序遍历，后序遍历），中序遍历不推荐

代码：

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

    public void swap(TreeNode cur) {
        TreeNode t = cur.left;
        cur.left = cur.right;
        cur.right = t;
    }
}

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

    public void swap(TreeNode cur) {
        TreeNode t = cur.left;
        cur.left = cur.right;
        cur.right = t;
    }
}

**法二：**层次遍历（遍历的过程中，使用根左右的顺序处理）

代码：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);

        while(!q.isEmpty()) {
            int size = q.size();
            for(int i = 0;i < size;i++) {
                TreeNode cur = q.poll();
                swap(cur);
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
        }

        return root;
    }

    public void swap(TreeNode cur) {
        TreeNode t = cur.left;
        cur.left = cur.right;
        cur.right = t;
    }
}

101.对称二叉树

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

思路: 递归, 分别判断外侧(左左, 右右) 和内侧(左右, 右左) 是否相等.

代码:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }

    public boolean compare(TreeNode left,TreeNode right) {
        if(left == null && right != null) return false;
        else if(left != null && right == null) return false;
        else if(left == null && right == null) return true;
        else if(left.val != right.val) return false;
        // 为空的情况已经全部被讨论过了, 此时一定不为空

        boolean out = compare(left.left,right.right);
        boolean in = compare(left.right,right.left);

        return out && in; // 外内必须全部相等
    }
}

100.相同的树

100. 相同的树

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

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

思路: 递归, 分别判断外侧(左左, 右左) 和内侧(左右, 右右) 是否相等.

代码:

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return compare(p,q);
    }

    public boolean compare(TreeNode left,TreeNode right) {
        if(left == null && right != null) return false;
        else if(left != null && right == null) return false;
        else if(left == null && right == null) return true;
        else if(left.val != right.val) return false;

        return compare(left.left,right.left) && compare(left.right,right.right);
    }
}

572.另一棵树的子树

572. 另一棵树的子树

思路: 先判断以root为根的树是否与另一棵相等, 再判断该树的左子树与另一棵树是否相等, 该树的右子树与另一棵树是否相等.

代码:

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) return false;
        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode root,TreeNode subRoot) {
        if(root == null && subRoot != null) return false;
        else if(root != null && subRoot == null) return false;
        else if(root == null && subRoot == null) return true;
        else if(root.val != subRoot.val) return false;

        return isSameTree(root.left,subRoot.left) && isSameTree(root.right,subRoot.right);
    }
}

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

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

法一: 递归法

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;// 结束条件
        return countNodes(root.left) + countNodes(root.right) + 1;// 递归逻辑: 左右中(后序遍历)
    }
}

法二 : 迭代法

class Solution {
    public int countNodes(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        int cnt = 0;
        while(!q.isEmpty()) {
            int size = q.size();
            while(size-- != 0) {
                TreeNode cur = q.poll();
                cnt++;
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
        }

        return cnt;
    }
}

法三: 递归法, 利用完全二叉树的特性

由于原来的数是一个完全二叉树，所以如果不为null, 一定含有满二叉树。只需要计算该树的最左侧的深度和最右侧的深度是否相等，即可判断该数是否为满二叉树，如果是满二叉树，则可以使用公式进行计算，如果不是满二叉树，则继续寻找满二叉树。

class Solution {
    public int countNodes(TreeNode root) {
        // 1. 递归终止条件
        if(root == null) return 0;

        // 2. 递归主要逻辑
        TreeNode l = root.left,r = root.right;
        int ldepth = 0,rdepth = 0;
        // 2.1 计算左子树的深度。
        while(l != null) {
            ldepth++;
            l = l.left;
        }
        // 2.2 计算右子树的深度
        while(r != null) {
            rdepth++;
            r = r.right;
        }
        // 2.3 如果ldepth==rdepth，则root所在是完全二叉树可以用公式2^n - 1
        if(ldepth == rdepth) return (2 << ldepth) - 1;
        // 2.4 所在的树不是完全二叉树, 则该数的节点数为 左子树的节点数+右子树的节点数+1。
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

110.平衡二叉树

110. 平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。

思路: 递归, 计算高度(后序遍历, 从下往上返回高度)

代码:

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getDepth(root) != -1;
    }

    public int getDepth(TreeNode cur) {
        // 1. 递归终止条件: cur == null, depth == 0
        if(cur == null) return 0;

        // 2. 递归主要逻辑
        // 2.1 左
        int ldepth = getDepth(cur.left);
        if(ldepth == -1) return -1;

        // 2.2 右
        int rdepth = getDepth(cur.right);
        if(rdepth == -1) return -1;
        
        // 2.3 中
        int res;
        if(Math.abs(ldepth - rdepth) > 1) return -1;
        else return Math.max(ldepth,rdepth) + 1;
    }
}

257.二叉树的所有路径

257. 二叉树的所有路径

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

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

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

**法一: **递归(显式回溯)

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,res,paths);
        return res;
    }

    public void traversal(TreeNode root,List<String> res,List<Integer> paths) {
        // 1. 中
        paths.add(root.val);

        // 2. 递归出口
        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;
        }

        // 3. 左
        if(root.left != null) {
            traversal(root.left,res,paths);
            paths.remove(paths.size() - 1);
        }
        
        // 4. 右
        if(root.right != null) {
            traversal(root.right,res,paths);
            paths.remove(paths.size() - 1);
        }
    }
}

法二: 递归(隐式回溯)

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

    public List<String> binaryTreePaths(TreeNode root) {
        // 定义容器, 开始遍历(前序遍历)
        if(root == null) return res;

        String path = "";
        traversal(path,root);
        return res;
    }

    public void traversal(String path,TreeNode root) {
        // 中
        if(root.left == null && root.right == null) {
            res.add(new StringBuilder(path).append(root.val).toString());
            return;
        }

        String tPath = new StringBuilder(path).append(root.val).append("->").toString();
        // 左
        if(root.left != null) traversal(tPath,root.left);
        // 右
        if(root.right != null) traversal(tPath,root.right);
    }
}

404.左叶子之和

404. 左叶子之和

思路: 后序遍历, 递归, 从符合条件的结点的父节点开始判断(要判断是否为左, 是否为叶子)

代码:

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        // 1. 递归出口
        if(root == null) return 0;
        // 2. 递归主要逻辑: 后序遍历, 往上层层返回
        // 2.1 左
        int leftVal = sumOfLeftLeaves(root.left);
        if(root.left != null && root.left.left == null && root.left.right == null) {
            leftVal = root.left.val;
        }
        // 2.2 右
        int rightVal = sumOfLeftLeaves(root.right);
        // 2.3 中
        int sum = leftVal + rightVal;
        return sum;
    }
}

513.找树左下角的值

513. 找树左下角的值

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

假设二叉树中至少有一个节点。

法一: 层次遍历

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        int res = 0;

        while(!q.isEmpty()) {
            int size = q.size();

            for(int i = 0;i < size;i++) {
                TreeNode cur = q.poll();
                if(i == 0) res = cur.val;
                // 不知道到底有多少层, 最后一层的0会将之前的结果覆盖

                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
        }

        return res;
    }
}

法二: 递归

class Solution {
    int maxDepth = -1;
    int res = Integer.MIN_VALUE;
    
    public int findBottomLeftValue(TreeNode root) {
        traversal(root,1);
        return res;
    }

    private void traversal(TreeNode cur,int depth) {
        // 1. 递归出口
        if(cur.left == null && cur.right == null) {
            if(depth > maxDepth) {// 如果遍历到同层右侧节点, if不成立, 不会再更新
                maxDepth = depth;
                res = cur.val;
                return;
            }
        }
        // 2. 主要逻辑: 确保左在右之前(保存左)
        if(cur.left != null) traversal(cur.left,depth + 1);
        if(cur.right != null) traversal(cur.right,depth + 1);
        return;
    }
}

112.路径总和

112. 路径总和

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

思路: 递归, 确保左在右之前

代码:

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        return traversal(root,targetSum - root.val);
    }

    public boolean traversal(TreeNode cur,int targetSum) {
        // 1. 递归出口: 叶子结点(对targetSum进行判断)
        if(cur.left == null && cur.right == null) {
            if(targetSum == 0) return true;
            return false;
        }
  

        // 2. 递归逻辑
        if(cur.left != null) {
            if(traversal(cur.left,targetSum - cur.left.val)) return true;
        }

        if(cur.right != null) {
            if(traversal(cur.right,targetSum - cur.right.val)) return true;
        }

        return false;
    }
}

113.路径总和 II

113. 路径总和 II

思路: 递归, 回溯, 要注意每次保存path必须是一个单独的list, 否则res中保存的path也会被影响

代码:

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

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root == null) return res;
        List<Integer> path = new ArrayList<>();

        traversal(root,targetSum - root.val,path);
        return res;
    }
    
    // 遍历所有节点, 不需要返回值
    public void traversal(TreeNode cur,int targetSum,List<Integer> path) {
        // 1. 递归出口: 叶子结点
        path.add(cur.val);
        if(cur.left == null && cur.right == null) {
            if(targetSum == 0) res.add(new ArrayList<>(path));// 单独的list
            return;
        }
        // 2. 递归主要逻辑
        if(cur.left != null) {
            traversal(cur.left,targetSum - cur.left.val,path);
            path.remove(path.size() - 1);// 回溯
        }

        if(cur.right != null) {
            traversal(cur.right,targetSum - cur.right.val,path);
            path.remove(path.size() - 1);// 回溯
        }
    }
}

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

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

法一: 递归, 数组分割

第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 1. 递归出口
        int n = postorder.length;
        if(n == 0) return null;

        // 2. 递归主要逻辑
        int rootVal = postorder[n - 1];
        int leftSize = indexOf(inorder,rootVal);// leftSize 为root的下标

        // 2.1 分割中序遍历数组
        int[] in1 = Arrays.copyOfRange(inorder,0,leftSize);// [l,r)
        int[] in2 = Arrays.copyOfRange(inorder,leftSize + 1,n);
        // 2.2 分割后序遍历数组
        int[] post1 = Arrays.copyOfRange(postorder,0,leftSize);
        int[] post2 = Arrays.copyOfRange(postorder,leftSize,n - 1);
        // 2.3 递归
        TreeNode left = buildTree(in1,post1);
        TreeNode right = buildTree(in2,post2);
        return new TreeNode(rootVal,left,right);
    }

    public int indexOf(int[] inorder,int val) {
        for(int i = 0;;i++) {
            if(inorder[i] == val) return i;
        }
    }
}

法二: map

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

        return f(inorder,0,inorder.length - 1,postorder,0,postorder.length - 1,map);
    }

    public TreeNode f(int[] inorder,int l1,int r1,int[] postorder,int l2,int r2,Map<Integer,Integer> map) {
        if(l2 > r2) return null;
        int rootVal = postorder[r2];
        TreeNode root = new TreeNode(rootVal);
        if(l2 == r2) return root;

        int k = map.get(rootVal);
        //              leftSize = k - l1           边界=起点+个数-1
        root.left = f(inorder,l1,k - 1,postorder,l2,l2 + k - l1 - 1,map);
        root.right = f(inorder,k + 1,r1,postorder,l2 + k - l1,r2 - 1,map);
        return root;
    }
}

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

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

法一: 递归, 数组分割

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 1. 递归出口
        int n = preorder.length;
        if(n == 0) return null;
        // 2. 递归主要逻辑
        int rootVal = preorder[0];
        int leftSize = indexOf(inorder,rootVal);
        // 2.1 分割左子树
        int[] pre1 = Arrays.copyOfRange(preorder,1,1 + leftSize);
        int[] in1 = Arrays.copyOfRange(inorder,0,leftSize);

        // 2.2 分割右子树
        int[] pre2 = Arrays.copyOfRange(preorder,1 + leftSize,n);
        int[] in2 = Arrays.copyOfRange(inorder,leftSize + 1,n);
        // 2.3 构造节点, 返回
        TreeNode left = buildTree(pre1,in1);
        TreeNode right = buildTree(pre2,in2);
        return new TreeNode(rootVal,left,right);
    }

    public int indexOf(int[] inorder,int val) {
        for(int i = 0;;i++) {
            if(inorder[i] == val) return i;
        }
    }
}

法二: 根据map定位下标

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 根据题目条件, 不会出现preorder inorder长度不能构造二叉树的情况
        // 1. 收集中序遍历的值和下标, 以便根据inorder的rootVal查找下标, 进行分割
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < inorder.length;i++) {
            map.put(inorder[i],i);
        }
        // 2. 开始递归
        return f(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1,map);
    }

    public TreeNode f(int[] preorder,int l1,int r1, int[] inorder,int l2,int r2,Map<Integer,Integer> map) {
        // 1. 递归出口: 无法构成TreeNode
        if(l1 > r1) return null;
        // 2. 创建头结点
        int rootVal = preorder[l1];
        TreeNode root = new TreeNode(rootVal);
        // 2.1 若只有一个节点, 直接返回
        if(l1 == r1) return root;
        // 2.2 递归创建二叉树
        int k = map.get(rootVal);// rootIndex
        // 		l1+1 + k-l2+1 == l1 + k - l2
        root.left = f(preorder,l1+1,l1 + k - l2,inorder,l2,k - 1,map);
        root.right = f(preorder,l1 + k - l2 + 1,r1,inorder,k + 1,r2,map);
        return root;
    }
}

654.最大二叉树

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums_ 构建的_ 最大二叉树 。

思路: 构造二叉树都需要前序遍历, 先建根节点, 再建左子树, 再建右子树。注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。

代码:

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return f(nums,0,nums.length - 1);
    }

    public TreeNode f(int[] nums,int left,int right) {
        // 1. 递归出口: 没有元素
        if(left > right) return null;

        // 2. 递归主要逻辑
        // 2.1 根
        // 注意maxVal和index取值, 不能都为0
        // 若值都为0, 下标0可能不在有效数组范围内, 但有效数组中的只有一个0, 直接使用数组第一个元素初始化
        int maxVal = nums[left];
        int index = left;
        for(int i = left + 1;i <= right;i++) {
            if(maxVal < nums[i]) {
                maxVal = nums[i];
                index = i;
            }
        }

        TreeNode root = new TreeNode(maxVal);
        // 2.2 左
        root.left = f(nums,left,index - 1);
        // 2.3 右
        root.right = f(nums,index + 1,right);
        return root;
    }
}

617.合并二叉树

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始.

思路: 同步遍历两棵二叉树

代码:

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 1. 递归出口: 一个为空, 则返回另一个(另一个不为空则有值, 另一个为空就为null)
        if(root1 == null) return root2;
        if(root2 == null) return root1;

        // 2. 递归主要逻辑: 前序遍历(根左右), 复用root1
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

700.二叉搜索树中的搜索

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

法一: 递归

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // 1. 出口
        if(root == null || root.val == val) return root;
        // 2. 单层逻辑
        if(val < root.val) return searchBST(root.left,val);
        else return searchBST(root.right,val);
    }
}

法二: 迭代

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

        return root;
    }
}

98.验证二叉搜索树

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

思路: 递归(双指针), 中序遍历, 按照遍历顺序(大小顺序) 进行比较 , 注意null也是二叉搜索树, 二叉搜索树中不能有相等的值

代码:

class Solution {
    private long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        // 1. 递归出口
        if(root == null) return true;
        
        // 2. 递归主要逻辑: 中序遍历, 比较大小
        boolean left = isValidBST(root.left);

        if(root.val <= prev) {
            return false;
        }else {
            prev = root.val;
        }

        boolean right = isValidBST(root.right);

        return left && right;
    }
}

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

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

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

思路: 递归, 中序遍历, 双指针

代码:

class Solution {
    TreeNode pre = null;// 记录前一个节点
    int res = Integer.MAX_VALUE;// 记录结果, 要求的是最小绝对差, 所以初始化为最大值

    public int getMinimumDifference(TreeNode root) {
        if(root == null) return 0;
        
        traversal(root);
        return res;
    }

    public void traversal(TreeNode root) {
        // 1. 出口
        if(root == null) return;
        // 2. 中序遍历
        traversal(root.left);

        if(pre != null) {
            res = Math.min(res,root.val - pre.val);
        }
        pre = root;

        traversal(root.right);
    }
}

501.二叉搜索树中的众数

501. 二叉搜索树中的众数

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

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

假定 BST 满足如下定义：

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

思路: 同上, 每次的cnt用maxCnt进行比较和统计, 每次的>=maxCnt的值都会收集, 一旦出现>maxCnt的情况, 则清空之前收集的所有值, 更新maxCnt和收集的值

代码:

class Solution {
    List<Integer> res = new ArrayList<>();
    int cnt = 0, maxCnt = 0;
    TreeNode pre = null;

    public int[] findMode(TreeNode root) {
        if(root == null) return new int[0];

        traversal(root);
        int[] ans = new int[res.size()];
        for(int i = 0;i < res.size();i++) {
            ans[i] = res.get(i);
        }

        return ans;
    }

    public void traversal(TreeNode cur) {
        // 1. 递归出口
        if(cur == null) return;

        // 2. 单层逻辑: 中序遍历
        // 2.1 左
        traversal(cur.left);

        // 2.2 中
        // 2.2.1 更新cnt, pre
        if(pre == null) {// 第一个节点
            cnt = 1;
        }else if(pre.val == cur.val) {// 遇到相同节点
            cnt++;
        }else {
            cnt = 1;// 遇到不同节点
        }
        // 2.2.2 收集, 更新maxCnt
        pre = cur;

        if(cnt == maxCnt) {
            res.add(cur.val);
        }else if(cnt > maxCnt) {
            maxCnt = cnt;
            res.clear();
            res.add(cur.val);
        }
        
        // 2.3 右
        traversal(cur.right);
    }
}

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

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

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

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

思路: 递归, 后序遍历, 从后往前递归找公共祖先

代码:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode cur, TreeNode p, TreeNode q) {
        // 1. 递归出口
        // 找到无效节点 || 找到其中一个节点:祖先为结点本身
        if(cur == null || cur == p || cur == q) return cur;

        // 2. 递归主要逻辑: 根据返回的结点返回祖先
        TreeNode left = lowestCommonAncestor(cur.left,p,q);
        TreeNode right = lowestCommonAncestor(cur.right,p,q);
        if(left != null && right != null) {// p,q在left/right之一
            return cur;
        }else if(left != null && right == null) {// p,q在left
            return left;
        }else if(left == null && right != null) {// p,q在right
            return right;
        }else return null;// p,q不存在left/right

    }   
}

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

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

法一: 同236

法二: 按照二叉搜索树的特性递归

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

法三: 根据二叉搜索树的性质迭代

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
            if(root.val > p.val && root.val > q.val) {
                root = root.left;
            }else if(root.val < p.val && root.val < q.val) {
                root = root.right;
            }else break;
        }

        return root;
    }
}

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

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

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

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

法一: 递归

class Solution {
    // 返回插入后新树的根节点
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);

        if(root.val > val) root.left = insertIntoBST(root.left,val);
        if(root.val < val) root.right = insertIntoBST(root.right,val);
        return root;
    }
}

法二: 迭代法, 双指针

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) return new TreeNode(val);

        // 记录前一个节点, 便于链接
        TreeNode pre = null;
        TreeNode cur = root;

        // 找到链接新结点的位置
        while(cur != null) {
            pre = cur;
            if(cur.val > val) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }

        // 开始链接新结点
        if(pre.val > val) pre.left = new TreeNode(val);
        if(pre.val < val) pre.right = new TreeNode(val);

        // 返回根节点
        return root;
    }
}

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

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

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

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

思路: 递归

有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点
- 第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

代码:

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 1. 递归出口
        // 1.1 当前节点为null
        if(root == null) return null;
        // 1.2 当前节点为要删除的结点
        if(root.val == key) {
            if(root.left == null) {// 左右都为空 左为空
                return root.right;
            }else if(root.right == null) {// 右为空
                return root.left;
            }else {// 左右都不为null
                TreeNode node = root.right;
                while(node.left != null) {
                    node = node.left;
                }
                node.left = root.left;
                return root.right; // 此时的node已经被改变, 不再是初值root.right
            }
        }
        // 2. 单层递归逻辑: 找目标节点进行删除
        if(root.val > key) root.left = deleteNode(root.left,key);
        if(root.val < key) root.right = deleteNode(root.right,key);
        return root;
    }
}

669.修剪二叉搜索树

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

思路: 递归修改子树

代码:

class Solution {
    // 返回修改后二叉树的根节点
    public TreeNode trimBST(TreeNode root, int low, int high) {
        // 1. 递归出口: 遇到null无法修剪 / 值越界需要修剪
        if(root == null) return null;
        if(root.val < low) return trimBST(root.right,low,high);
        if(root.val > high) return trimBST(root.left,low,high);
        // 2. 单层递归逻辑: 该节点连接修改后的子树
        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;        
    }
}

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

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

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵

平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

思路: 递归, 找到数组中间位置, 中间位置作为根节点, 用左部分递归建立左子树, 右部分递归建立右子树.

代码:

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums,0,nums.length - 1);
    }

    public TreeNode traversal(int[] nums,int left,int right) {
        if(left > right) return null;

        // 1. 找到数组中间位置
        int mid = left + ((right - left) >> 1);
        // int mid = left + (right - left >> 1);
        // 注: 位运算符要加括号, 默认优先级在+-*/之后
        TreeNode root = new TreeNode(nums[mid]);
        // 2. 分割数组
        root.left = traversal(nums,left,mid - 1);
        root.right = traversal(nums,mid + 1,right);
        return root;
    }
}

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

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

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

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

思路: 双指针, pre记录前一个要累加的节点值(若为node处理不好可能空指针), cur指向当前要进行累加的节点

代码:

class Solution {
    public int pre = 0;

    public TreeNode convertBST(TreeNode root) {
        traversal(root);
        return root;
    }

    public void traversal(TreeNode root) {
        if(root == null) return;
        // 右
        traversal(root.right);
        // 中
        root.val += pre;
        pre = root.val;
        // 左
        traversal(root.left);
    }
}