代码随想录_二叉树

二叉树

二叉树的递归遍历

• 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;// basecaseres.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, queueList<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, queueList<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, queueList<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, queueList<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, queueList<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 - 1if(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 == 0if(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));// 单独的listreturn;}// 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           边界=起点+个数-1root.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. 递归出口: 无法构成TreeNodeif(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 - l2root.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 递归地构建:

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

返回 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. 递归主要逻辑: 前序遍历(根左右), 复用root1root1.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, preif(pre == null) {// 第一个节点cnt = 1;}else if(pre.val == cur.val) {// 遇到相同节点cnt++;}else {cnt = 1;// 遇到不同节点}// 2.2.2 收集, 更新maxCntpre = 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在leftreturn left;}else if(left == null && right != null) {// p,q在rightreturn 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 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

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

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

思路: 递归

有以下五种情况：

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

代码:

class Solution {public TreeNode deleteNode(TreeNode root, int key) {// 1. 递归出口// 1.1 当前节点为nullif(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 {// 左右都不为nullTreeNode 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);}
}