1-leetcode94. 二叉树的中序遍历
注意:√
- 递归方法已经很熟练了,两种不同的递归方式
- 迭代法需要注意,
zrm
就遇到了要求迭代实现,前序遍历和后续遍历其实不难,中序遍历用的少,注意看一看
// 1.递归方法1
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
traverse(root);
return res;
}
private void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.left);
// 中序位置
res.add(root.val);
traverse(root.right);
}
// 2.递归方法2
public List<Integer> inorderTraversal1(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
res.addAll(inorderTraversal1(root.left));
res.add(root.val);
res.addAll(inorderTraversal1(root.right));
return res;
}
// 3.迭代方法
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.add(cur);
cur = cur.left;
}else {
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}
2-leetcode104. 二叉树的最大深度
注意:√
- 动态规划思想,秒杀
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;
}
3-leetcode226. 翻转二叉树
注意:√
- 递归的思想,注意一下要提前保存左右的节点索引
public TreeNode invertTree(TreeNode root) {
if (root == null){
return null;
}
TreeNode leftNode = root.left;
TreeNode rightNode = root.right;
root.left = invertTree(rightNode);
root.right = invertTree(leftNode);
return root;
}
4-leetcode101. 对称二叉树
注意:×
- 建议直接使用队列的方式,不过注意加入队列的方式,很巧妙
左左,右右, 左右, 右左
public boolean isSymmetric(TreeNode root) {
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root.left);
queue.add(root.right);
while (queue.size()>0){
TreeNode le = queue.pollFirst();
TreeNode ri = queue.pollFirst();
if (le == null && ri == null){
continue;
}
if (le == null || ri == null){
return false;
}
if (le.val != ri.val) {
return false;
}
queue.add(le.left);
queue.add(ri.right);
queue.add(le.right);
queue.add(ri.left);
}
return true;
}
5-leetcode543. 二叉树的直径
注意:×
- 学习Labuladong,这题可以由maxDepth转过来
- 注意的地方是,这个题目要的是二叉树的直径,也就是路径值,路径值和深度需要体会一下
- 直径长就是左右两个深度加起来
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
int x = maxDepth(root);
return res;
}
public int maxDepth(TreeNode root) {
if (root == null){
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
int curDepth = leftDepth + rightDepth;
res = Math.max(curDepth, res);
return Math.max(leftDepth, rightDepth) +1;
}
6-leetcode102. 二叉树的层序遍历
注意:××
- 注意加入
queue
的时候,要判断是不是空 while
循环判断是不是空,不要用size
会浪费时间- 最开始就给
res = new LinkedList
这样判断root == null
的时候可以直接返回结果
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null){
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
// while (queue.size()>0){
while (! queue.isEmpty()){
int num = queue.size();
List<Integer> list = new LinkedList<>();
for (int i = 0; i < num; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null){
queue.add(node.left);
}
if (node.right != null){
queue.add(node.right);
}
}
res.add(list);
}
return res;
}
leetcode
注意:√×