226. 翻转二叉树
101. 对称二叉树
递归法
两颗树的遍历顺序分别是左右中和右左中，因此本质上是一个后序遍历
public boolean compare(TreeNode left, TreeNode right){if (left == null && right == null) return true;else if (left == null && right != null) return false;else if (left != null && right == null) return false;else if (left.val != right.val) return false;//比较外侧boolean outside = compare(left.left, right.right);//比较内侧boolean inside = compare(left.right, right.left);return outside && inside;}
迭代法
使用双端队列或者普通队列皆可
public boolean isSymmetric(TreeNode root) {Deque<TreeNode> deque = new LinkedList<>();deque.addFirst(root.left);deque.addLast(root.right);while (!deque.isEmpty()){TreeNode left = deque.pollFirst();TreeNode right = deque.pollLast();if (left == null && right == null) continue;if (left == null && right != null) return false;if (left != null && right == null) return false;if (left.val != right.val) return false;//此时left.val == right.valdeque.offerFirst(left.left);deque.offerFirst(left.right);deque.offerLast(right.right);deque.offerLast(right.left);}return true;}
104. 二叉树的最大深度
递归法
最大深度为根节点到最远叶子节点的最长路径上的节点数
迭代法用层序遍历，递归法用后序遍历，主要学习递归法，分别求取左右子树的最大深度，再加一即可
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;
}
迭代法
public int maxDepth(TreeNode root) {
if (root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()){
int len = queue.size();
depth++;
while(len-- > 0){
TreeNode node = queue.poll();
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}
}
return depth;
}
111. 二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量
- 个人思路：使用层序遍历，如果当层结点小于当层应该有的结点即2的n次方，那么该层即为最小深度。但是这样不符合最小深度的定义
- 关键在于叶子结点，得左右孩子都为空的结点才算到头
递归法
如果不加中间的判断，没有左孩子的分支会算为最短深度。
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
最后，如果左右子树都不为空，返回左右子树深度最小值 + 1 。
public int minDepth(TreeNode root){
if (root == null){
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) return rightDepth + 1;
if (root.right == null) return leftDepth + 1;
return Math.min(leftDepth, rightDepth) + 1;
}
迭代法
public int minDepth1(TreeNode root) {
if (root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()){
depth ++;
int len = queue.size();
while(len-- > 0){
TreeNode node = queue.poll();
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
if (node.left == null && node.right == null){
return depth;
}
}
}
return depth;
}
222. 完全二叉树的节点个数
递归法：左子树结点个数+右子树结点个数+当前结点（即 + 1）
public int countNodes(TreeNode root) {
if (root == null){
return 0;
}
int leftNodes = countNodes(root.left) ;
int rightNodes = countNodes(root.right);
return leftNodes+rightNodes + 1;
}
110. 平衡二叉树
首先明确深度和高度的定义，详见二叉树基础
❌自顶向下的递归
类似前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。也是我的思路，但是这种方法，在同一个节点处，height方法会被重复调用，递归套递归
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null){
return true;
}
int leftDepth = getHeight(root.left);
int rightDepth = getHeight(root.right);
if (Math.abs(leftDepth - rightDepth) > 1){
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
}
🌟自底向上的递归
类似后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1−1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) > 0;
}
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(node.left);
if(leftHeight == -1)
return -1;
int rightHeight = getHeight(node.right);
if(rightHeight == -1)
return -1;
int result;
if(Math.abs(leftHeight - rightHeight) > 1){
result = -1;
}else {
result = Math.max(leftHeight, rightHeight) + 1;
}
return result;
}
}
257. 二叉树的所有路径
从根节点到子结点—>前序遍历，所有路径—>回溯
递归法
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
List<Integer> paths = new ArrayList<>();
if (root == null){
return res;
}
traversal(root, res, paths);
return res;
}
public void traversal(TreeNode root, List<String> res, List<Integer> paths){
paths.add(root.val);
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)); //多加一个->再delete是不行的，因为只会删一个字符
res.add(sb.toString());
return ;
}
if (root.left != null){
traversal(root.left, res, paths); //做出选择
paths.remove(paths.size() - 1); //撤销选择
}
if (root.right != null){
traversal(root.right, res, paths);
paths.remove(paths.size() - 1);
}
}
}
迭代法
class Solution {
/**
* 迭代法
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root == null)
return result;
Stack<Object> stack = new Stack<>();
// 节点和路径同时入栈
stack.push(root);
stack.push(root.val + "");
while (!stack.isEmpty()) {
// 节点和路径同时出栈
String path = (String) stack.pop();
TreeNode node = (TreeNode) stack.pop();
// 若找到叶子节点
if (node.left == null && node.right == null) {
result.add(path);
}
//右子节点不为空
if (node.right != null) {
stack.push(node.right);
stack.push(path + "->" + node.right.val);
}
//左子节点不为空
if (node.left != null) {
stack.push(node.left);
stack.push(path + "->" + node.left.val);
}
}
return result;
}
}
404. 左叶子之和
「如果左节点不为空，且左节点没有左右孩子，那么这个节点的左节点就是左叶子」
递归法
public int sumOfLeftLeaves(TreeNode root) {
if(root == null){
return 0;
}
int left = sumOfLeftLeaves(root.left);
int right = sumOfLeftLeaves(root.right);
int mid = 0;
if(root.left != null && root.left.left == null && root.left.right == null){
mid = root.left.val;
}
return left + right + mid;
}
迭代法
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
Stack<TreeNode> stack = new Stack<> ();
stack.add(root);
int result = 0;
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null && node.left.left == null && node.left.right == null) {
result += node.left.val;
}
if (node.right != null) stack.add(node.right);
if (node.left != null) stack.add(node.left);
}
return result;
}
513. 找树左下角的值
递归法
int maxDepth = -1;
int maxDepthLeft = 0;
public int findBottomLeftValue(TreeNode root){
traversal(root, 0);
return maxDepthLeft;
}
public void traversal(TreeNode root, int leftDepth){
if (root.left == null && root.right == null) {
if (leftDepth > maxDepth) {
maxDepth = leftDepth;
maxDepthLeft = root.val;
}
return ;
}
if (root.left != null) {
leftDepth++;
traversal(root.left, leftDepth);
leftDepth--;
}
if (root.right != null) {
traversal(root.right, leftDepth + 1);//隐藏着回溯
}
}
迭代法
public int findBottomLeftValue(TreeNode root) {
int res = 0;
ArrayDeque<TreeNode> dq = new ArrayDeque<>();
dq.addLast(root);
while(!dq.isEmpty()){
int len = dq.size();
res = dq.peekFirst().val;
while(len-- > 0){
TreeNode node = dq.pollFirst();
if(node.left != null){
dq.addLast(node.left);
}
if(node.right != null){
dq.addLast(node.right);
}
}
}
return res;
}
112. 路径总和
递归法
- 使用count表示还需要的目标值
递归的返回值是boolean
class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) { return false; } return traversal(root, targetSum - root.val); } public boolean traversal(TreeNode root, int count) { if (root.left == null && root.right == null) { return count == 0; } if (root.left != null) { if (traversal(root.left, count - root.left.val)) { return true; } } if (root.right != null) { if (traversal(root.right, count - root.right.val)){ return true; } } return false; } }迭代法
public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) { return false; } ArrayDeque<TreeNode> stack1 = new ArrayDeque<>(); ArrayDeque<Integer> stack2 = new ArrayDeque<>(); stack1.addLast(root); stack2.addLast(root.val); while (!stack1.isEmpty()) { int size = stack1.size(); while (size-- > 0) { TreeNode node = stack1.pollLast(); int sum = stack2.pollLast(); if (node.left == null && node.right == null && sum == targetSum) { return true; } if (node.right != null) { stack1.addLast(node.right); stack2.addLast(sum + node.right.val); } if (node.left != null) { stack1.addLast(node.left); stack2.addLast(sum + node.left.val); } } } return false; }113. 路径总和 II
递归法
class Solution { List<List<Integer>> res = new ArrayList<>(); Deque<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int targetSum) { if (root == null) { return res; } path.add(root.val); traversal(root, targetSum - root.val); return res; } public void traversal(TreeNode root, int count) { if (root.left == null && root.right == null) { if (count == 0) { res.add(new ArrayList<>(path)); } return ; } if (root.left != null) { path.add(root.left.val); count -= root.left.val; traversal(root.left, count); count += root.left.val; path.removeLast(); } if (root.right != null) { path.add(root.right.val); count -= root.right.val; traversal(root.right, count); count += root.right.val; path.removeLast(); } } }
若有收获，就点个赞吧
0 人点赞
