《代码随想录》刷题笔记——二叉树篇【java实现】

二叉树遍历

前、中、后序遍历

• 前序：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

• 中序：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

• 后序：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

递归法求解

三种遍历，只是节点取值顺序有调整而已：

• 前序：取值 | 遍历左子树 | 遍历右子树
• 中序：遍历左子树 | 取值 | 遍历右子树
• 后序：遍历左子树 | 遍历右子树 | 取值

前序遍历

/*** 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<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traversal(root, result);return result;}private void traversal(TreeNode cur, List<Integer> result) {if (cur == null) return;result.add(cur.val);traversal(cur.left, result);traversal(cur.right, result);}
}

中序遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traversal(root, result);return result;}private void traversal(TreeNode cur, List<Integer> result) {if (cur == null)return;traversal(cur.left, result);result.add(cur.val);traversal(cur.right, result);}
}

后序遍历

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();traversal(root, result);return result;}private void traversal(TreeNode cur, List<Integer> result) {if (cur == null)return;traversal(cur.left, result);traversal(cur.right, result);result.add(cur.val);}
}

迭代遍历法求解

前序遍历※

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);while (!stack.isEmpty()) {// 每次循环从栈中取出一个节点存储到结果集中TreeNode pop = stack.pop();result.add(pop.val);// 如果当前取出的节点，存在左右节点，则将其存储到栈中。// 注意，先存储右节点，再存储左节点，因为栈的特性是先进后出if (pop.right != null) stack.push(pop.right);if (pop.left != null) stack.push(pop.left); }return result;
}

代码执行过程可以参考如下图片，每个红框表示一次循环的操作

中序遍历※

思路：

1、初始化栈：创建一个空栈。

2、遍历左子树：从根节点开始，如果当前节点有左子节点，则将当前节点压入栈中，并将当前节点设置为其左子节点，继续遍历左子树，直到到达叶子节点。

3、处理节点：当没有左子节点时，从栈中弹出一个节点，访问该节点（例如，将其值添加到结果集合中）。

4、遍历右子树：检查刚刚弹出的节点是否有右子节点。如果有，将当前节点设置为该右子节点，并返回第2步继续遍历；如果没有，继续从栈中弹出节点，重复第3步，直到栈为空或弹出的节点有右子节点。

初始实现：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Deque<TreeNode> stack = new ArrayDeque<>();TreeNode cur = root;stack.push(cur);while (cur != null && !stack.isEmpty()) {if (cur.left != null) {// --if-- 如果当前节点还有左节点，将其加入栈中stack.push(cur.left);cur = cur.left;}else {// 从栈中不断弹出元素，直到弹出的元素，右节点不为空while (!stack.isEmpty()) {TreeNode pop = stack.pop();result.add(pop.val);if (pop.right != null) {// --if-- 当前节点有右节点，开始遍历右节点stack.push(pop.right);cur = pop.right;break;}}}}return result;
}

优化代码：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Deque<TreeNode> stack = new ArrayDeque<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {// 首先，将所有左子节点入栈while (cur != null) {stack.push(cur);cur = cur.left;}// 当前节点为空，说明到达叶子节点的左侧，开始出栈并处理节点cur = stack.pop();result.add(cur.val);// 处理右子树cur = cur.right;}return result;
}

代码随想录版本：

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

后序遍历※

前序遍历是中左右，后续遍历是左右中。只需要先将前序遍历的代码改成中右左，再将得到的result反转即可。

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);while (!stack.isEmpty()) {// 每次循环从栈中取出一个节点存储到结果集中TreeNode pop = stack.pop();result.add(pop.val);// 这里要模拟中右左，先存储左节点，再存储右节点，因为栈的特性是先进后出if (pop.left != null) stack.push(pop.left);if (pop.right != null) stack.push(pop.right);}Collections.reverse(result);return result;
}

层序遍历

102. 二叉树的层序遍历

迭代法

按照上面的方式可以将节点的数值按照层遍历出来了，但是题目要求结果需要分层来存储。因此我使用一个变量来记录下一层的节点数量，这样循环下层的时候，可以知道下层的节点数量，进而将该层的节点全部从队列中取出来

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;Deque<TreeNode> deque = new ArrayDeque<>();deque.addFirst(root);int num = 1;// 用来记录下层的节点数量int addNum;while (!deque.isEmpty()) {List<Integer> layer = new ArrayList<>();addNum = 0;while (num-- > 0) {// 把当前层的节点全部取出来TreeNode treeNode = deque.pollLast();layer.add(treeNode.val);if (treeNode.left != null) {deque.addFirst(treeNode.left);// 下层的节点数量++addNum++;}if (treeNode.right != null) {deque.addFirst(treeNode.right);// 下层的节点数量++addNum++;}}result.add(layer);num = addNum;}return result;
}

如果使用LinkedList来作为队列的话，就不需要记录下一层的节点数了，因为LinkedList提供了.size()方法

 public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;while (!queue.isEmpty()) {List<Integer> layer = new ArrayList<>();// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();layer.add(treeNode.val);if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}result.add(layer);}return result;
}

递归法

public List<List<Integer>> levelOrder2(TreeNode root) {List<List<Integer>> result = new ArrayList<>();recursion(result, root, 0);return result;
}private void recursion(List<List<Integer>> result, TreeNode node, int deep) {if (node == null) return;if (deep >= result.size()) {result.add(new ArrayList<>());}result.get(deep).add(node.val);recursion(result, node.left, ++deep);recursion(result, node.right, deep);
}

107. 二叉树的层序遍历 II

public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;while (!queue.isEmpty()) {List<Integer> layer = new ArrayList<>();// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();layer.add(treeNode.val);if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}// 唯一的区别result.add(0,layer);}return result;
}

199. 二叉树的右视图

public List<Integer> rightSideView(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) return result;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;int num = 0;while (!queue.isEmpty()) {// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();num = treeNode.val;if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}result.add(num);}return result;
}

637.二叉树的层平均值

https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/

每层计算一下平均值即可

public List<Double> averageOfLevels(TreeNode root) {List<Double> result = new ArrayList<>();if (root == null) return result;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;while (!queue.isEmpty()) {double sum = 0;// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();sum += treeNode.val;if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}result.add(sum / layerNum);}return result;
}

429. N 叉树的层序遍历

public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;LinkedList<Node> queue = new LinkedList<>();queue.add(root);int layerNum;while (!queue.isEmpty()) {List<Integer> layer = new ArrayList<>();// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {Node treeNode = queue.pollLast();layer.add(treeNode.val);for (Node child : treeNode.children) {if (child != null) {queue.addFirst(child);}}}result.add(layer);}return result;
}

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

public Node connect(Node root) {if (root == null) return root;LinkedList<Node> queue = new LinkedList<>();queue.add(root);int layerNum;while (!queue.isEmpty()) {// 当前层的节点数量layerNum = queue.size();Node lastNode = null;for (int i = 0; i < layerNum ; i++) {Node treeNode = queue.pollLast();if (lastNode != null) {lastNode.next = treeNode;}lastNode = treeNode;if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}}return root;
}

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

1. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

遍历法

每遍历一层，深度+1

public int maxDepth(TreeNode root) {if (root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;int depth = 0;while (!queue.isEmpty()) {// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}depth++;}return depth;
}

递归法

public int maxDepth(TreeNode root) {if (root == null) return 0;return dfs(root, 1);
}private int dfs(TreeNode cur, int depth) {if (cur.left != null && cur.right != null) {return Math.max(dfs(cur.left, depth + 1), dfs(cur.right, depth + 1));} else if (cur.left != null) {return dfs(cur.left, depth + 1);} else if (cur.right != null) {return dfs(cur.right, depth + 1);} else {return depth;}
}

递归法效率高一点

111. 二叉树的最小深度

public int minDepth(TreeNode root) {if (root == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;int depth = 0;while (!queue.isEmpty()) {// 当前层的节点数量layerNum = queue.size();boolean isStop = false;for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}// 找到叶子节点，说明该层是最小深度if (treeNode.left == null && treeNode.right == null) {isStop = true;break;}}depth++;if (isStop == true) {break;}}return depth;
}

morris遍历（了解即可）

翻转二叉树

递归法

这道题使用前序遍历或者后续遍历都很容易解决，其实就是遍历的时候，反转一下所遍历节点的左右子节点即可

【前序遍历】

• 前序：交换左右子节点 | 遍历左子树 | 遍历右子树

public TreeNode invertTree(TreeNode root) {dfs(root);return root;
}private void dfs(TreeNode node) {if (node == null) {return;}// 交换左右子节点TreeNode temp = node.left;node.left = node.right;node.right = temp;// 遍历左子树dfs(node.left);// 遍历右子树dfs(node.right);
}

【后序遍历】

• 后序： 遍历左子树 | 遍历右子树 | 交换左右子节点

public TreeNode invertTree(TreeNode root) {dfs(root);return root;
}private void dfs(TreeNode node) {if (node == null) {return;}dfs(node.left);dfs(node.right);TreeNode temp = node.left;node.left = node.right;node.right = temp;
}

【中序】

中序会产生什么问题呢？

一开始递归搜索了left，然后交换之后，right变成了left，最后再递归right，其实本质也是递归left

dfs(node.left);TreeNode temp = node.left;
node.left = node.right;
node.right = temp;dfs(node.right);

因此如果需要使用中序遍历，需要在交换之后，还是对left进行递归

class Solution {public TreeNode invertTree(TreeNode root) {dfs(root);return root;}private void dfs(TreeNode node) {if (node == null) {return;}dfs(node.left);TreeNode temp = node.left;node.left = node.right;node.right = temp;dfs(node.left);}
}

迭代法

在层序遍历的基础上，交换一下左右子节点即可

public TreeNode invertTree1(TreeNode root) {if (root == null) return root;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;while (!queue.isEmpty()) {List<Integer> layer = new ArrayList<>();// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();layer.add(treeNode.val);if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}// 交换左右子节点TreeNode temp = treeNode.left;treeNode.left = treeNode.right;treeNode.right = temp;}}return root;
}

对称二叉树

递归法

【字符串记录树的值】

root的左右子树分别递归，用字符串记录树的值

public boolean isSymmetric(TreeNode root) {StringBuilder s1 = new StringBuilder();StringBuilder s2 = new StringBuilder();leftDfs(s1, root.left);rightDfs(s2, root.right);System.out.println(s1.toString());System.out.println(s2.toString());return s1.toString().equals(s2.toString());
}private void leftDfs(StringBuilder s, TreeNode node) {if (node == null) {s.append("n");return;}s.append(node.val);leftDfs(s, node.left);leftDfs(s, node.right);
}private void rightDfs(StringBuilder s, TreeNode node) {if (node == null) {s.append("n");return;}s.append(node.val);rightDfs(s, node.right);rightDfs(s, node.left);
}

效率很低

【两颗子树一起递归】

public boolean isSymmetric(TreeNode root) {return dfs(root.left, root.right);
}private boolean dfs(TreeNode left, TreeNode right) {if (left != null && right != null) {// --if-- left和right都不为null，判断当前两个节点的值是否相同，并进一步判断节点的子节点是否相同return left.val == right.val && dfs(left.left, right.right) && dfs(left.right, right.left);} else if (left == right) {// --if-- left和right都是nullreturn true;} else {// --if-- left和right一个为null，一个不为null，肯定返回falsereturn false;}
}

迭代法

public boolean isSymmetric(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root.left);queue.addFirst(root.right);while (!queue.isEmpty()) {TreeNode node1 = queue.pollLast();TreeNode node2 = queue.pollLast();if (node1 == node2) {// --if-- 两个节点都是nullcontinue;} else if (node1 != null && node2 != null && node1.val == node2.val) {// --if-- 两个节点都不为null，且值相同queue.addFirst(node1.left);queue.addFirst(node2.right);queue.addFirst(node1.right);queue.addFirst(node2.left);continue;}// 有一个节点为null，或两个节点值相同return false;}return true;
}

完全二叉树的节点个数

递归法

public int countNodes(TreeNode node) {if (node == null) {return 0;}// 当前节点计数为1int num = 1;// 加上左子树的节点数量num += countNodes(node.left);// 加上右子树的节点数量num += countNodes(node.right);return num;
}

代码再简化

public int countNodes(TreeNode node) {if (node == null) {return 0;}// 当前节点计数为1+左子树的节点数量+右子树的节点数量return 1 + countNodes(node.left) + countNodes(node.right);
}

迭代法

public int countNodes(TreeNode root) {if (root == null) return 0;Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);int num = 0;while (!stack.isEmpty()) {// 每次循环从栈中取出一个节点存储到结果集中TreeNode pop = stack.pop();num++;// 如果当前取出的节点，存在左右节点，则将其存储到栈中。// 注意，先存储右节点，再存储左节点，因为栈的特性是先进后出if (pop.right != null) stack.push(pop.right);if (pop.left != null) stack.push(pop.left);}return num;
}

平衡二叉树

递归法 ※

该题可以借鉴二叉树的最大深度，当左右子树不平衡的时候，可以返回-1

public boolean isBalanced(TreeNode root) {return recursion(root, 0) != -1;
}private int recursion(TreeNode cur, int depth) {if (cur == null) {return depth;}// 计算左子树的深度int leftDepth = recursion(cur.left, depth + 1);if (leftDepth == -1) {// 左子树不是平衡二叉树，返回-1return -1;}// 计算右子树的深度int rightDepth = recursion(cur.right, depth + 1);if (rightDepth == -1) {// 右子树不是平衡二叉树，返回-1return -1;}if (leftDepth < rightDepth - 1 || leftDepth > rightDepth + 1) {// 如果左右子树深度差 大于 1，说明当前节点的树为非平衡二叉树return -1;}return Math.max(leftDepth, rightDepth);
}

迭代法

其实就是两个层序遍历，一个用来求高度，还有一个则用来调用求高度方法来判断左右节点高度是否相差大于1。该方式效率较低，节点被遍历了多次（每次求高度都需要遍历子树的所有节点），时间复杂度O(n^2)

public boolean isBalanced1(TreeNode root) {if (root == null) return true;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int layerNum;int depth = 0;while (!queue.isEmpty()) {// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();if (Math.abs(getHeight(treeNode.left) - getHeight(treeNode.right)) > 1) {return false;}if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}depth++;}return true;
}public int getHeight(TreeNode node) {if (node == null) return 0;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(node);int layerNum;int depth = 0;while (!queue.isEmpty()) {// 当前层的节点数量layerNum = queue.size();for (int i = 0; i < layerNum; i++) {TreeNode treeNode = queue.pollLast();if (treeNode.left != null) {queue.addFirst(treeNode.left);}if (treeNode.right != null) {queue.addFirst(treeNode.right);}}depth++;}return depth;
}

优化版本

• 针对暴力迭代法的getHeight方法做优化，利用TreeNode.val（这个字段本身没有被使用）来保存当前节点的高度，这样就不会有重复遍历
• 获取高度算法时间复杂度可以降到O(1)，总的时间复杂度降为O(n)

【算法思路】

• 有左节点，先遍历左节点
• 左节点遍历完成，有右节点的话，再遍历右节点
• 左右节点都遍历完成之后，计算左右子树的高度差，判断是否为平衡二叉树

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 curNode = stack.peek();// 右节点为null或已经遍历过if (curNode.right == null || curNode.right == pre) {// 输出if (Math.abs(getHeight(curNode.left) - getHeight(curNode.right)) > 1) {return false;}// 计算完高度差之后，再将当前遍历节点弹出stack.pop();// 记录所遍历到的节点pre = curNode;// 当前节点下，没有要遍历的节点了，因为右节点也遍历过了root = null;} else {// 右节点还没遍历，遍历右节点root = curNode.right;}}return true;
}/*** 求节点的高度* 计算当前节点高度的前提是，当前节点的左右子树高度已经计算过，所以使用中序遍历*/
public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = root.left != null ? root.left.val : 0;int rightHeight = root.right != null ? root.right.val : 0;// 用TreeNode.val来保存当前节点的高度root.val =  Math.max(leftHeight, rightHeight) + 1;return root.val;
}

如果看代码有点懵逼，可以看下面图的迭代流程，每个蓝框都是一次循环

二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/description/

递归法

public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();recursion(root, res, "");return res;
}private void recursion(TreeNode node, List<String> res, String str) {if (node != null) {str += "->" + node.val;if (node.left == null && node.right == null) {res.add(str.substring(2));}recursion(node.left, res, str);recursion(node.right, res, str);}
}

因为上面使用的是String来拼接路径，效率比较低

【改进】

public List<String> binaryTreePaths1(TreeNode root) {List<String> res = new ArrayList<>();List<Integer> path = new ArrayList<>();recursion1(root, res, path);return res;
}private void recursion1(TreeNode node, List<String> res, List<Integer> path) {if (node != null) {path.add(node.val);if (node.left == null && node.right == null) {// --if-- 当前节点已经是叶子节点，存储路径// 使用StringBuilder拼接比直接使用String拼接更快StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < path.size() - 1; i++) {stringBuilder.append(path.get(i)).append("->");}stringBuilder.append(path.get(path.size() - 1));res.add(stringBuilder.toString());}recursion1(node.left, res, path);recursion1(node.right, res, path);
//            System.out.println(path.toString());// 删掉当前递归深度添加的数字path.remove(path.size() - 1);}
}

为什么要删除最后一个节点，假如不删除的话，下图的结果是1->2->5、1->2->5->3

假如放开上面的输出，输出结果如下

[1]
[1, 2]
[1, 2, 5]
[1, 3]

递归的过程如图所示

迭代法

在前序遍历迭代法的基础上面修改，使用栈同时记录节点和节点对应的路径

public List<String> binaryTreePaths2(TreeNode root) {List<String> result = new ArrayList<>();if (root == null) return result;Deque<Object> stack = new ArrayDeque<>();stack.push(root);stack.push(root.val + "");while (!stack.isEmpty()) {String path = (String) stack.pop();TreeNode cur = (TreeNode) stack.pop();if (cur != null) {if (cur.left == null && cur.right == null) {result.add(path);}// 如果当前取出的节点，存在左右节点，则将其存储到栈中。// 注意，先存储右节点，再存储左节点，因为栈的特性是先进后出if (cur.right != null) {stack.push(cur.right);stack.push(path + "->" + cur.right.val);}if (cur.left != null) {stack.push(cur.left);stack.push(path + "->" + cur.left.val);}}}return result;
}

相同的树

https://leetcode.cn/problems/same-tree/

递归法

解法和对称二叉树基本是一样的，树1的左和树2的左比，树1的右和树2的右比就行

public boolean isSameTree(TreeNode node1, TreeNode node2) {if (node1 != null && node2 != null) {// --if-- node1和node2都不为null，判断当前两个节点的值是否相同，并进一步判断节点的子节点是否相同return node1.val == node2.val && isSameTree(node1.left, node2.left) && isSameTree(node1.right, node2.right);} else if (node1 == node2) {// --if-- node1和node2都是nullreturn true;} else {// --if-- node1和node2一个为null，一个不为null，肯定返回falsereturn false;}
}

迭代法

public boolean isSameTree(TreeNode node1, TreeNode node2) {LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(node1);queue.addFirst(node2);while (!queue.isEmpty()) {node1 = queue.pollLast();node2 = queue.pollLast();if (node1 == node2) {// --if-- 两个节点都是nullcontinue;} else if (node1 != null && node2 != null && node1.val == node2.val) {// --if-- 两个节点都不为null，且值相同queue.addFirst(node1.left);queue.addFirst(node2.left);queue.addFirst(node1.right);queue.addFirst(node2.right);continue;}// 有一个节点为null，或两个节点值相同return false;}return true;
}

左叶子之和

https://leetcode.cn/problems/sum-of-left-leaves/description/

递归法 ※

public int sumOfLeftLeaves(TreeNode node) {if (node == null) {return 0;}if (node.left != null && node.left.left == null && node.left.right == null) {// 如果当前节点的左节点不为null，但是左节点没有子节点，加上该节点的值return node.left.val + sumOfLeftLeaves(node.right);}return sumOfLeftLeaves(node.left) + sumOfLeftLeaves(node.right);
}

迭代法

public int sumOfLeftLeaves1(TreeNode root) {int sum = 0;Deque<TreeNode> stack = new ArrayDeque<>();stack.push(root);while (!stack.isEmpty()) {// 每次循环从栈中取出一个节点存储到结果集中TreeNode node = stack.pop();if (node.left != null && node.left.left == null && node.left.right == null) {// 如果当前节点的左节点不为null，但是左节点没有子节点，加上该节点的值sum+= node.left.val;}// 如果当前取出的节点，存在左右节点，则将其存储到栈中。// 注意，先存储右节点，再存储左节点，因为栈的特性是先进后出if (node.right != null) stack.push(node.right);if (node.left != null) stack.push(node.left);}return sum;
}

找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/description/

递归法

最简单的方法，使用全局变量，当遍历到到比targetDeep的节点时，更新targetVal的值

private int targetDeep;
private int targetVal;public int findBottomLeftValue(TreeNode root) {targetDeep = -1;recursion(root, 0);return targetVal;
}private void recursion(TreeNode cur, int deep) {if (cur == null) return;if (deep > targetDeep) {targetVal = cur.val;targetDeep = deep;}recursion(cur.left, deep + 1);recursion(cur.right, deep + 1);
}

迭代法

直接层序遍历，遍历到每层的第一个节点时，更新值即可

public int findBottomLeftValue2(TreeNode root) {if (root == null) return 0;int targetNum = 0;Deque<TreeNode> deque = new ArrayDeque<>();deque.addFirst(root);int num = 1;// 用来记录下层的节点数量int addNum;TreeNode treeNode;while (!deque.isEmpty()) {addNum = 0;// 为什么上面的代码不放在循环里面，就是为了少一个判断for (int i = 0; i < num; i++) {// 把当前层的节点全部取出来treeNode = deque.pollLast();if (i == 0) {targetNum = treeNode.val;}if (treeNode.left != null) {deque.addFirst(treeNode.left);// 下层的节点数量++addNum++;}if (treeNode.right != null) {deque.addFirst(treeNode.right);// 下层的节点数量++addNum++;}}num = addNum;}return targetNum;
}

可以做一点点优化，减少一个判断，就是代码冗余一点

public int findBottomLeftValue1(TreeNode root) {if (root == null) return 0;int targetNum = 0;Deque<TreeNode> deque = new ArrayDeque<>();deque.addFirst(root);int num = 1;// 用来记录下层的节点数量int addNum;while (!deque.isEmpty()) {addNum = 0;// 将每层的第一个节点的值存储起来TreeNode treeNode = deque.pollLast();targetNum = treeNode.val;if (treeNode.left != null) {deque.addFirst(treeNode.left);// 下层的节点数量++addNum++;}if (treeNode.right != null) {deque.addFirst(treeNode.right);// 下层的节点数量++addNum++;}// 为什么上面的代码不放在循环里面，就是为了少一个判断for (int i = 1; i < num; i++) {// 把当前层的节点全部取出来treeNode = deque.pollLast();if (treeNode.left != null) {deque.addFirst(treeNode.left);// 下层的节点数量++addNum++;}if (treeNode.right != null) {deque.addFirst(treeNode.right);// 下层的节点数量++addNum++;}}num = addNum;}return targetNum;
}

路径总和

递归法

/*** 判断是否可以找到等于总和的路径* @param node* @param leftNum 剩余的树* @return*/
public boolean hasPathSum(TreeNode node, int leftNum) {if (node == null) {return false;}if (node.left == null && node.right == null && leftNum == node.val) {// --if-- 如果当前节点为叶子节点，且节点值正好等于剩余数字return true;}// 左子树和右子树中能找到一条路径，即可返回truereturn hasPathSum(node.left, leftNum - node.val) || hasPathSum(node.right, leftNum - node.val);
}

迭代法 ※

使用一个numStack来记录上一个节点的总和

public boolean hasPathSum1(TreeNode root, int targetNum) {if (root == null) return false;Deque<TreeNode> stack = new ArrayDeque<>();Deque<Integer> numStack = new ArrayDeque<>();stack.addFirst(root);numStack.addFirst(0);int num = 1;// 用来记录下层的节点数量int addNum;TreeNode treeNode;while (!stack.isEmpty()) {addNum = 0;// 为什么上面的代码不放在循环里面，就是为了少一个判断for (int i = 0; i < num; i++) {// 把当前层的节点全部取出来treeNode = stack.pollLast();int totalNum = numStack.pollLast();int curNum = totalNum + treeNode.val;if (treeNode.left == null && treeNode.right == null && curNum == targetNum) {return true;}if (treeNode.left != null) {stack.addFirst(treeNode.left);numStack.push(curNum);// 下层的节点数量++addNum++;}if (treeNode.right != null) {stack.addFirst(treeNode.right);numStack.push(curNum);// 下层的节点数量++addNum++;}}num = addNum;}return false;
}

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

思路

首先需要思考中序遍历和后续遍历的顺序。

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

从上面可以挖掘出什么样的信息呢？

• 后序遍历的数组最后一个元素，一定是最顶层的节点，即根节点

• 题目中说明了数组中没有重复的值，那我们可以用后续遍历数组的最后一个数字，来找到一个位置，来将中序遍历得到数组划分为两个部分，第一个部分是根节点的左子节点，第二个部分则是根节点的右子节点

• 划分完前序遍历数组之后，还需要处理一下后续遍历数组。

• 来到这里第一层就处理完毕了。接下来就是用 inorder = [9] 和 postorder = [9] 确定左子树； 用 inorder = [15,20,7] 和 postorder = [15,7,20] 来确定右子树。划分为两个子树之后，下面又是一样的递归流程了。

实现

public TreeNode buildTree(int[] inorder, int[] postorder) {return recursion(inorder, postorder, 0, inorder.length, 0, postorder.length);
}private TreeNode recursion(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {if (inStart >= inEnd || postStart >= postEnd) {return null;}TreeNode treeNode = new TreeNode(postorder[postEnd - 1]);// 找到划分中序遍历数组的点int inSplitIndex = -1;for (int i = inStart; i < inEnd; i++) {if (inorder[i] == postorder[postEnd - 1]) {inSplitIndex = i;break;}}// 找到划分后序遍历数组的点int postSplitIndex = postStart + (inSplitIndex - inStart);// 递归处理左子树treeNode.left = recursion(inorder, postorder, inStart, inSplitIndex, postStart, postSplitIndex);// 递归处理右子树treeNode.right = recursion(inorder, postorder, inSplitIndex + 1, inEnd, postSplitIndex , postEnd - 1);return treeNode;
}

【优化】

因为数组的元素是唯一的，可以使用字典来存储值和相应索引，避免每次需要循环寻找索引

public TreeNode buildTree1(int[] inorder, int[] postorder) {HashMap<Integer, Integer> valueAndIndexMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {valueAndIndexMap.put(inorder[i], i);}return recursion1(inorder, postorder, 0, inorder.length, 0, postorder.length, valueAndIndexMap);
}private TreeNode recursion1(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd, HashMap<Integer, Integer> valueAndIndexMap) {if (inStart >= inEnd || postStart >= postEnd) {return null;}TreeNode treeNode = new TreeNode(postorder[postEnd - 1]);// 找到划分中序遍历数组的点int inSplitIndex = valueAndIndexMap.get(postorder[postEnd - 1]);// 找到划分后序遍历数组的点int postSplitIndex = postStart + (inSplitIndex - inStart);// 递归处理左子树treeNode.left = recursion1(inorder, postorder, inStart, inSplitIndex, postStart, postSplitIndex, valueAndIndexMap);// 递归处理右子树treeNode.right = recursion1(inorder, postorder, inSplitIndex + 1, inEnd, postSplitIndex, postEnd - 1, valueAndIndexMap);return treeNode;
}

思考题

• 知道后序遍历的数组和中序遍历的数组可以唯一确定一棵二叉树。
• 知道前序遍历的数组和中序遍历的数组也可以唯一确定一棵二叉树。
• 但**前序和后序不能唯一确定一棵二叉树，**因为没有中序遍历无法确定左右部分。

最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/description/

求解

public TreeNode constructMaximumBinaryTree(int[] nums) {return recursion(nums, 0, nums.length);
}private TreeNode recursion(int[] nums, int start, int end) {if (end <= start) {return null;} else if (end == start + 1) {return new TreeNode(nums[start]);}int maxIndex = -1;// 由题目可知，数值的取值是[0,1000]int maxValue = -1;// 注意：循环的时候是左开右闭for (int i = start; i < end; i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxIndex = i;}}TreeNode treeNode = new TreeNode(maxValue);// 因为是左开右闭，所以右边传入maxIndextreeNode.left = recursion(nums, start, maxIndex);treeNode.right = recursion(nums, maxIndex + 1, end);return treeNode;
}

合并二叉树

递归法

public TreeNode mergeTrees(TreeNode node1, TreeNode node2) {if (node1 == null) {// --if-- node1为空，直接返回node2return node2;} else if (node2 == null) {return node1;} else {// --if-- 两个节点都不为空，将node2的值添加到node1上面node1.val += node2.val;// 处理左节点node1.left = mergeTrees(node1.left, node2.left);// 处理右节点node1.right = mergeTrees(node1.right, node2.right);}return node1;
}

迭代法 ※

public TreeNode mergeTrees(TreeNode node1, TreeNode node2) {if (node1 == null) {// --if-- node1为空，直接返回node2return node2;} else if (node2 == null) {return node1;}Deque<TreeNode> stack = new ArrayDeque<>();stack.push(node1);stack.push(node2);while (!stack.isEmpty()) {// 每次循环从栈中取出一个节点存储到结果集中TreeNode pop2 = stack.pop();TreeNode pop1 = stack.pop();pop1.val += pop2.val;if (pop1.left != null && pop2.left != null) {stack.push(pop1.left);stack.push(pop2.left);} else if (pop1.left == null && pop2.left != null) {pop1.left = pop2.left;}if (pop1.right != null && pop2.right != null) {stack.push(pop1.right);stack.push(pop2.right);} else if (pop1.right == null && pop2.right != null) {pop1.right = pop2.right;}}return node1;
}

二叉搜索树中的搜索

https://leetcode.cn/problems/search-in-a-binary-search-tree/description/

递归法

public TreeNode searchBST(TreeNode node, int val) {if (node == null) {return null;}if (node.val == val) {return node;}// 递归看看左节点是否符合条件TreeNode left = searchBST(node.left, val);if (left != null) {// --if-- 左节点符合，直接返回，无需再往下遍历右节点return left;}return searchBST(node.right, val);
}

递归法（适配二叉搜索树）

【注意】该树是二叉搜索树

• 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

因此，只遍历左右子树中的一个即可

public TreeNode searchBST2(TreeNode node, int val) {if (node == null) {return null;}if (node.val == val) {return node;} else if (node.val > val) {return searchBST(node.left, val);}else {return searchBST(node.right, val);}
}

迭代法

public TreeNode searchBST1(TreeNode node, int val) {if (node == null) {return null;}Deque<TreeNode> queue = new ArrayDeque<>();queue.push(node);while (!queue.isEmpty()) {TreeNode poll = queue.poll();if (poll.val == val) {return poll;}if (poll.right != null) {queue.push(poll.right);}if (poll.left != null) {queue.push(poll.left);}}return null;
}

迭代法（适配二叉搜索树）

public TreeNode searchBST(TreeNode node, int val) {if (node == null) {return null;}Deque<TreeNode> queue = new ArrayDeque<>();queue.push(node);while (!queue.isEmpty()) {TreeNode poll = queue.poll();if (poll.val == val) {return poll;} else if (poll.val > val) {// --if-- 当前节点值大于val，往左子树搜索即可if (poll.left != null) queue.push(poll.left);} else {// --if-- 当前节点值大于val，往左子树搜索即可if (poll.right != null) queue.push(poll.right);}}return null;
}

验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/description/

递归法（前序遍历）

【基础实现】

• 要判断一棵树是否为二叉搜索树，需要左子节点的最大值<当前节点的值，右子节点的最小值>当前节点值
• 使用一个对象来存储一颗树的最大、最小值

class Value {/*** 当前节点对应子树的最大节点值*/int max;/*** 当前节点对应子树的最小节点值*/int min;/*** 当前节点对应二叉树是否满足二叉搜索树要求*/boolean isReasonable;public Value(int max, int min, boolean isReasonable) {this.max = max;this.min = min;this.isReasonable = isReasonable;}
}public boolean isValidBST(TreeNode root) {return recursion(root).isReasonable;
}private Value recursion(TreeNode node) {if (node.left == null && node.right == null) {// --if-- 左右子节点都为空时，树的最大最小值都为当前节点的值return new Value(node.val, node.val, true);}Value leftValue = null;if (node.left != null) {leftValue = recursion(node.left);if (leftValue.isReasonable == false) {// --if-- 左子树不合法，直接返回return leftValue;}
//            System.out.println("当前节点值：" + node.val + " 左子树最大值：" + leftValue.max);if (leftValue.max >= node.val) {// --if-- 左子树的最大值大于等于当前节点的值，不合法，返回leftValue.isReasonable = false;return leftValue;}}Value rightValue = null;if (node.right != null) {rightValue = recursion(node.right);if (rightValue.isReasonable == false) {// --if-- 右子树不合法，直接返回return rightValue;}
//            System.out.println("当前节点值：" + node.val + " 右子树最小值：" + rightValue.min);if (rightValue.min <= node.val) {// --if-- 右子树的最小值小于等于当前节点的值，不合法，返回rightValue.isReasonable = false;return rightValue;}}return new Value(rightValue == null ? node.val : rightValue.max,leftValue == null ? node.val : leftValue.min,true);
}

多次提交性能不同

递归法（中序遍历）※

TreeNode max;
public boolean isValidBST(TreeNode node) {if (node == null) {return true;}// 左boolean left = isValidBST(node.left);if (!left) {return false;}// 中if (max != null && node.val <= max.val) {return false;}max = node;// 右return isValidBST(node.right);
}

如果二叉树为二叉搜索树的话，随着中序遍历的进行，max的值是一直递增的，如果node.val <= max.val，说明不满足二叉搜索树

迭代法（中序遍历）

和中序遍历迭代法代码差不多，获取元素的时候，比较一下大小就行

public boolean isValidBST(TreeNode root) {if (root == null) return false;Deque<TreeNode> stack = new ArrayDeque<>();TreeNode maxNode = null;TreeNode cur = root;stack.push(cur);while (cur != null && !stack.isEmpty()) {if (cur.left != null) {// --if-- 如果当前节点还有左节点，将其加入栈中stack.push(cur.left);cur = cur.left;} else {// 从栈中不断弹出元素，直到弹出的元素，右节点不为空while (!stack.isEmpty()) {TreeNode pop = stack.pop();if (maxNode != null && pop.val <= maxNode.val) {return false;}maxNode = pop;if (pop.right != null) {// --if-- 当前节点有右节点，开始遍历右节点stack.push(pop.right);cur = pop.right;break;}}}}return true;
}

二叉搜索树的最小绝对差

递归法（中序遍历）※

如果是二叉搜索树，牢牢记住中序遍历出来的数值是从小到大的，只需要依次比较前后两个节点值的差是否更小即可

private TreeNode lastNode;
private int min = Integer.MAX_VALUE;
private int temp;public int getMinimumDifference(TreeNode node) {if (node == null) {return 0;}// 遍历左子树getMinimumDifference(node.left);// 更新最小值if (lastNode != null) {temp = node.val - lastNode.val;if (temp < min) {min = temp;}}// 更新上一个所遍历的节点lastNode = node;// 遍历右子树getMinimumDifference(node.right);return min;
}

迭代法（中序遍历）

public int getMinimumDifference1(TreeNode node) {if (node == null) return 0;Deque<TreeNode> stack = new ArrayDeque<>();TreeNode lastNode = null;int minDiff = Integer.MAX_VALUE;int tempDiff;TreeNode cur = node;stack.push(cur);while (cur != null && !stack.isEmpty()) {if (cur.left != null) {// --if-- 如果当前节点还有左节点，将其加入栈中stack.push(cur.left);cur = cur.left;} else {// 从栈中不断弹出元素，直到弹出的元素，右节点不为空while (!stack.isEmpty()) {TreeNode pop = stack.pop();if (lastNode != null) {tempDiff = pop.val - lastNode.val;if (tempDiff < minDiff) {minDiff = tempDiff;}}lastNode = pop;if (pop.right != null) {// --if-- 当前节点有右节点，开始遍历右节点stack.push(pop.right);cur = pop.right;break;}}}}return minDiff;
}

二叉搜索树中的众数

递归法（中序遍历）

/*** 存储上一个节点*/
private TreeNode lastNode;
/*** 存储最高频*/
private int maxNum = 0;
/*** 记录当前数出现的频次*/
private int temp = 0;public int[] findMode(TreeNode root) {List<Integer> result = new ArrayList<>();recursion(result, root);int[] resultArr = new int[result.size()];for (int i = 0; i < result.size(); i++) {resultArr[i] = result.get(i);}return resultArr;
}public void recursion(List<Integer> result, TreeNode node) {if (node == null) {return;}// 遍历左子树recursion(result, node.left);// 更新最小值if (lastNode != null) {if (node.val != lastNode.val) {// --if-- 当前节点值和上一个节点值不同，temp计数改为1，即记录当前节点的频数temp = 1;} else {// --if-- 当前节点值和上一个节点值相同，temp计数++temp++;}if (temp > maxNum) {// --if-- 找到了更大频数的数// 清空原本的众数集合result.clear();// 将新的众数添加到结果集中result.add(lastNode.val);// 更新最新数量maxNum = temp;} else if (temp == maxNum) {// --if-- 当前数的频数和众数频数一样大，将其添加到众数结果集中result.add(node.val);}} else {// --if-- 中序遍历的第一个节点，添加到结果集中，temp和maxNum设置为1result.add(node.val);temp = 1;maxNum = 1;}// 更新上一个所遍历的节点lastNode = node;// 遍历右子树recursion(result, node.right);
}

迭代法（中序遍历）

public int[] findMode(TreeNode root) {List<Integer> resultList = new ArrayList<>();Deque<TreeNode> stack = new ArrayDeque<>();TreeNode lastNode = null;/*** 存储最高频*/int maxNum = 0;/*** 记录当前数出现的频次*/int temp = 0;TreeNode cur = root;stack.push(cur);while (cur != null && !stack.isEmpty()) {if (cur.left != null) {// --if-- 如果当前节点还有左节点，将其加入栈中stack.push(cur.left);cur = cur.left;} else {// 从栈中不断弹出元素，直到弹出的元素，右节点不为空while (!stack.isEmpty()) {TreeNode pop = stack.pop();// 更新最小值if (lastNode != null) {if (pop.val != lastNode.val) {// --if-- 当前节点值和上一个节点值不同，temp计数改为1，即记录当前节点的频数temp = 1;} else {// --if-- 当前节点值和上一个节点值相同，temp计数++temp++;}if (temp > maxNum) {// --if-- 找到了更大频数的数// 清空原本的众数集合resultList.clear();// 将新的众数添加到结果集中resultList.add(lastNode.val);// 更新最新数量maxNum = temp;} else if (temp == maxNum) {// --if-- 当前数的频数和众数频数一样大，将其添加到众数结果集中resultList.add(pop.val);}} else {// --if-- 中序遍历的第一个节点，添加到结果集中，temp和maxNum设置为1resultList.add(pop.val);temp = 1;maxNum = 1;}lastNode = pop;if (pop.right != null) {// --if-- 当前节点有右节点，开始遍历右节点stack.push(pop.right);cur = pop.right;break;}}}}int[] resultArr = new int[resultList.size()];for (int i = 0; i < resultList.size(); i++) {resultArr[i] = resultList.get(i);}return resultArr;
}

二叉树的最近公共祖先

递归法（后序遍历）※

private TreeNode fatherNode;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {recursion(root, p, q);return fatherNode;
}private TreeNode recursion(TreeNode node, TreeNode p, TreeNode q) {if (node == null) {return null;}TreeNode left = recursion(node.left, p, q);TreeNode right = recursion(node.right, p, q);if (left != null && right != null) {// --if-- 左右子树 都找到了p、q的一个，说明当前节点即为最近公开祖先fatherNode = node;return null;} else if ((left != null || right != null) && (node.val == p.val || node.val == q.val)) {// --if-- 左右子树 只找到了p、q的一个，且当前节点等于p、q的一个，说明当前节点即为最近公开祖先fatherNode = node;return null;}if (node.val == p.val || node.val == q.val) {// --if-- 当前节点为p、q中的一个，返回当前节点return node;} else if (left != null) {// --if-- 当前节点的左子树，返回了p、q中的一个，返回leftreturn left;} else if (right != null) {// --if-- 当前节点的左子树，返回了p、q中的一个，返回rightreturn right;}return null;
}

【代码优化】

public TreeNode lowestCommonAncestor1(TreeNode node, TreeNode p, TreeNode q) {if (node == null || node == p || node == q) { // --if-- 如果当前节点就是 p 或 q ，直接返回当前节点，不需要管后面有没有 p 或 q 的另一个return node;}TreeNode left = lowestCommonAncestor1(node.left, p, q);TreeNode right = lowestCommonAncestor1(node.right, p, q);if (left != null && right != null) {// --if-- 在左、右子树种分别找到了节点 p、q，说明当前节点即为最近公开祖先return node;} else if (left != null) {// --if-- 当前节点的左子树，返回了p、q中的一个，返回leftreturn left;} else if (right != null) {// --if-- 当前节点的左子树，返回了p、q中的一个，返回rightreturn right;} else {// --if-- 未找到节点 p、qreturn null;}
}