LeetCode 热题 HOT 100：https://leetcode.cn/problem-list/2cktkvj/
94. 二叉树的中序遍历 ---- 递归与非递归
题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
递归方式：
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
InOrder(root);
return list;
}
public void InOrder(TreeNode root){
if(root != null){
InOrder(root.left);
list.add(root.val);
InOrder(root.right);
}
}
}
非递归方式：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
List<Integer> list = new ArrayList<>();
TreeNode p = root;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else{
p = stack.pop();
list.add(p.val);
p = p.right;
}
}
return list;
}
}
补充：144. 二叉树的前序遍历 ---- 递归与非递归
题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
递归做法：
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return list;
}
public void preOrder(TreeNode root){
if(root != null){
list.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
}
}
非递归做法：
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
List<Integer> list = new ArrayList<>();
TreeNode p = root;
while(p != null || !stack.isEmpty()){
if(p != null){
list.add(p.val);
stack.push(p);
p = p.left;
}else{
p = stack.pop();
p = p.right;
}
}
return list;
}
}
补充：145. 二叉树的后序遍历 ---- 递归与非递归
题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
递归做法：
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
postOrder(root);
return list;
}
public void postOrder(TreeNode root){
if(root != null){
postOrder(root.left);
postOrder(root.right);
list.add(root.val);
}
}
}
非递归做法：
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p, r;
p = root;
r = null;
while(p != null || !stack.isEmpty()){
if(p != null){ // 走到最左边
stack.push(p);
p = p.left;
}else{ // 向右
p = stack.peek(); // 得到栈顶元素
if(p.right != null && p.right != r){ // 右子树存在，且未访问
p = p.right;
}else{ // 否则弹出节点并访问
p = stack.pop();
list.add(p.val);
r = p; // 记录最近访问节点
p = null; // 节点访问后，重置 p
}
}
}
return list;
}
}
96. 不同的二叉搜索树
题目链接：https://leetcode.cn/problems/unique-binary-search-trees/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
动态规划：
- 假设
n 个节点存在二叉搜索树的个数是 G(n)，令 f(i) 为以 i 为根的二叉排序树的个数，则：G(n) = f(1) + f(2) + … + f(n-1) + f(n)
- 当
i 为根节点时，由于是二叉搜索树，则其左子树节点个数为 i-1 个，右子树节点为 n-i 个，得：f(i) = G(i-1) * G(n-i)
- 综上可得卡特兰数的公式：
G(n) = f(1) + f(2) + … + f(n-1) + f(n)
= G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-2) * G(1) + G(n-1) * G(0)
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1]; // dp[i] 代表 i 个节点存在二叉搜索树的个数
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i ++){
for(int j = 0; j < i; j ++){
dp[i] += dp[j]*dp[i-1-j];
}
}
return dp[n];
}
}
98. 验证二叉搜索树
题目链接：https://leetcode.cn/problems/validate-binary-search-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
递归中序遍历：
class Solution {
long max = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
if(!isValidBST(root.left)){
return false;
}
if(root.val <= max){
return false;
}else{
max = root.val;
}
return isValidBST(root.right);
}
}
非递归中序遍历：
class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
List<Integer> list = new ArrayList<>();
TreeNode p = root;
long max = Long.MIN_VALUE;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}else{
p = stack.pop();
if (p.val <= max){
return false;
}else{
max = p.val;
}
list.add(p.val);
p = p.right;
}
}
return true;
}
}
101. 对称二叉树
题目链接：https://leetcode.cn/problems/symmetric-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return false;
}
return recur(root.left, root.right);
}
public boolean recur(TreeNode l, TreeNode r){
if(l == null && r == null){
return true;
}
if(l == null || r == null || l.val != r.val){
return false;
}
return recur(l.left, r.right) && recur(l.right, r.left);
}
}
102. 二叉树的层序遍历
题目链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
双端队列模拟队列实现层序遍历：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Deque<TreeNode> queue = new LinkedList<>();
if(root != null){
queue.push(root);
}
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
for(int i = queue.size(); i > 0; i --){ // // 注意避坑点：queue.size()，在出队时会发生变化，因此实现用 i 记录队列长度，倒序循环
TreeNode p = queue.remove();
list.add(p.val);
if(p.left != null){
queue.add(p.left);
}
if(p.right != null){
queue.add(p.right);
}
}
res.add(list);
}
return res;
}
}
104. 二叉树的最大深度
题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
深搜DFS：
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;
}
}
广搜BFS：
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
Deque<TreeNode> queue = new LinkedList<>();
TreeNode p = root;
int depth = 0;
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = queue.size(); i > 0; i --){
p = queue.remove();
if(p.left != null){
queue.add(p.left);
}
if(p.right != null){
queue.add(p.right);
}
}
depth++;
}
return depth;
}
}
105. 从前序与中序遍历序列构造二叉树
题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) { // 先序，中序
return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}
public TreeNode build(int[] preorder, int lpre, int rpre, int[] inorder, int lmid, int rmid){ // 先序左边界、右边界，中序左边界、右边界
if(lmid>rmid || lpre>rpre){
return null;
}
TreeNode node = new TreeNode(preorder[lpre]);
int fa = lpre; // fa代表中序遍历数组中的根节点的索引
for(int i = lmid; i <= rmid; i ++){
if(inorder[i] == preorder[lpre]){
fa = i;
break;
}
}
int len = fa-lmid; // 左子树的长度
// 先序（根左右）：左边界+1、左边界+长度，中序（左根右）：左边界、根节点位置-1
node.left = build(preorder, lpre+1, lpre+len, inorder, lmid, fa-1);
// 先序（根左右）：左边界+长度+1、右边界，中序（左根右）：根节点位置+1、右边界
node.right = build(preorder, lpre+len+1, rpre, inorder, fa+1, rmid);
return node;
}
}
参考思路：团体程序设计天梯赛-练习集 L2-011 玩转二叉树 (25分) 先序中序建树 思路详解
114. 二叉树展开为链表
题目链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
原始做法： 将节点前序遍历存储在集合当中，然后对集合中的节点依次展开。
class Solution {
public void flatten(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p = root;
List<TreeNode> list = new LinkedList<>();
while(p!=null||!stack.isEmpty()){
if(p!=null){
stack.push(p);
list.add(p);
p = p.left;
}else{
p = stack.pop();
p = p.right;
}
}
TreeNode q = root;
for (int i = 1; i < list.size(); i++) {
q.left = null;
q.right = list.get(i);
q = list.get(i);
}
}
}
优化后做法：利用先序遍历 根左右 的特点。将根的右侧指向左子树，左子树的最右节点指向原来根的右子树，并将左子树置为空。
class Solution {
public void flatten(TreeNode root) {
TreeNode curr = root; // 当前节点指向根
while(curr != null){
if(curr.left != null){
TreeNode next = curr.left; // 左子树
TreeNode pre = next;
while(pre.right != null){ // 查询左子树的最右节点
pre = pre.right;
}
pre.right = curr.right; // 最右节点的右指针指向当前节点的右子树
curr.right = next; // 当前节点的右子树指向当前节点的左子树的根
curr.left = null; // 当前节点左子树置为空
}
curr = curr.right;
}
}
}
124. 二叉树中的最大路径和
题目链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
- 二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。最大的路径，可能的路径情况：
a
/ \
b c
① b + a + c。
② b + a + a 的父结点。（需要再次递归）
③ a + c + a 的父结点。（需要再次递归）
- 其中情况 1，表示如果不联络父结点的情况，或本身是根结点的情况。这种情况是没法递归的，但是结果有可能是全局最大路径和，因此可以在递归过程中通过比较得出。
- 情况 2 和 3，递归时计算 a+b 和 a+c，选择一个更优的方案返回，也就是上面说的递归后的最优解。
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root == null){
return 0;
}
dfs(root);
return max;
}
/**
* 返回经过root的单边分支最大和， 即 Math.max(root, root+left, root+right)
*/
public int dfs(TreeNode root){
if(root == null){
return 0;
}
// 计算左子树最大值，左边分支如果为负数还不如不选择
int leftMax = Math.max(0, dfs(root.left));
// 计算右子树最大值，右边分支如果为负数还不如不选择
int rightMax = Math.max(0, dfs(root.right));
// left->root->right 作为路径与已经计算过历史最大值做比较
max = Math.max(max, leftMax + root.val + rightMax);
// 返回经过root的单边最大分支给当前root的父节点计算使用
return root.val + Math.max(leftMax, rightMax);
}
}
参考：【二叉树中的最大路径和】递归，条理清晰
226. 翻转二叉树
题目链接：https://leetcode.cn/problems/invert-binary-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
递归做法：
class Solution {
public TreeNode invertTree(TreeNode root) {
overturnTree(root);
return root;
}
public void overturnTree(TreeNode root){
if(root == null){
return;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
overturnTree(root.left);
overturnTree(root.right);
}
}
非递归做法： 利用层次遍历，在每层放入队列之后，交换左右节点。
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode p = queue.remove();
if(p.left != null){
queue.add(p.left);
}
if(p.right != null){
queue.add(p.right);
}
TreeNode tmp = p.left;
p.left = p.right;
p.right = tmp;
}
return root;
}
}
538. 把二叉搜索树转换为累加树
题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
递归做法：
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
order(root);
return root;
}
public void order(TreeNode root){
if(root!=null){
order(root.right);
sum += root.val;
root.val = sum;
order(root.left);
}
}
}
非递归做法：
class Solution {
public TreeNode convertBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode p = root;
int sum = 0;
while(!stack.isEmpty() || p != null){ // 反中序遍历
if(p!=null){
stack.push(p);
p = p.right;
}else{
p = stack.pop();
sum += p.val;
p.val = sum;
p = p.left;
}
}
return root;
}
}
543. 二叉树的直径
题目链接：https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
左右节点深度加一起就是最大路径：
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
maxDepth(root);
return max;
}
public int maxDepth(TreeNode root){
if(root == null){
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
max = Math.max(max, leftDepth + rightDepth); // 左右节点深度加一起就是最大路径
return Math.max(leftDepth, rightDepth) + 1;
}
}
617. 合并二叉树
题目链接：https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
return merge(root1, root2);
}
public TreeNode merge(TreeNode root1, TreeNode root2){
if(root1 == null && root2 == null){
return null;
}else if(root1 == null){
return root2;
}else if(root2 == null){
return root1;
}else{
root1.val += root2.val;
root1.left = merge(root1.left, root2.left);
root1.right = merge(root1.right, root2.right);
return root1;
}
}
}
