代码随想录day14 | leetcode 226.翻转二叉树 101. 对称二叉树 104.二叉树的最大深度 111.二叉树的最小深度

226.翻转二叉树

前序和后序写法都可以 我用的是前序
错误写法

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

为什么 swap 方法不起作用？

Java 的参数传递机制是 按值传递，即传递的是变量的值，而不是引用本身。对于引用类型（如 TreeNode），传递的是引用的副本。因此：

1. 在 swap(TreeNode left, TreeNode right) 中交换 left 和 right 时，只是交换了局部变量 left 和 right，不会影响传入的 root.left 和 root.right。
2. root.left 和 root.right 的实际值在方法外部并没有改变。
   正确写法

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

在递归中，是否需要 return null; 或仅仅 return;两种情况的区别：

1. void 方法：直接 return;

在 void 方法中，比如 swap(TreeNode node)，方法本身不需要返回任何值。
因此，当递归到终止条件时，仅仅用 return; 即可终止当前递归调用，并让控制流回到上一层。
示例：

public void swap(TreeNode node) {
    if (node == null) return; // 递归终止，退出当前方法
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;
}

• return; 的作用：退出当前方法，没有返回值。
• 为什么不需要 return null;？ 因为方法的返回类型是 void，本来就不能返回值，return; 就足够。

2. 有返回值的方法：需要返回值，比如 return null;

在返回类型不是 void 的递归方法中（比如 TreeNode invertTree(TreeNode root)），必须按照方法签名返回一个与返回类型一致的值。如果递归的终止条件是空节点（root == null），此时返回值应该是 null。
示例：

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null; // 递归终止，返回 null
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root; // 返回当前节点
}

• return null; 的作用：在递归中明确表示当前子树为空，用于返回递归终止的结果。
• 为什么不能只用 return;？ 因为方法的返回类型是 TreeNode，return; 不符合类型要求。

理解两者的适用场景

什么时候用 return null;？

• 方法有返回值（非 void），比如 TreeNode。
• 表示递归的终止条件，并且需要将结果（比如 null）传递回上一层递归调用。

什么时候用 return;？

• 方法是 void 类型，不需要返回任何值。
• 表示递归的终止条件，仅仅退出当前方法即可。

101.对称二叉树

只能用后序遍历 因为先获取中值无法进行后续比较

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 CompareOutside = compare(left.left, right.right); //比较外侧
        boolean CompareInside = compare(left.right, right.left); //比较内侧
        return CompareInside && CompareOutside;
    }
}

不难 重要是打开思路 判断终止条件可以有很多

104.二叉树的最大深度

求高度用后序遍历，求深度用前序遍历

而根节点的高度就是二叉树的最大深度
在一棵二叉树中：

• 最大深度从根节点向下计算（从根到叶子）。
• 高度从叶子节点向上计算（从叶子到根）。
  因此，根节点的高度就等于整棵树的最大深度。

104.二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftheight = maxDepth(root.left);
        int rightheight = maxDepth(root.right);
        int height = 1 + Math.max(leftheight,rightheight);
        return height;
    }
}

---

559.n叉树的最大深度

class Solution {
    public int maxDepth(Node root) {
        if(root == null) return 0;

        int depth = 0;
        if(root.children != null) {
            for(Node child : root.children) {
                depth = Math.max(depth,maxDepth(child));
            }
        }
        return 1 + depth;
    }
}

后序遍历的定义

后序遍历（Post-order Traversal）是指：

1. 首先递归处理左子树（或子树的所有子节点）。
2. 然后递归处理右子树（或子树的其他子节点）。
3. 最后处理当前节点。

对于 N 叉树来说，后序遍历就是：

1. 先递归处理每个子节点。
2. 最后处理当前节点（计算当前节点的深度）。

• 递归顺序：
  • 当我们调用 maxDepth(child) 时，我们是先计算子节点的深度，递归地访问每个子节点。这个部分类似于后序遍历的 “先处理子节点”。
  • 当所有子节点都被访问过后，代码才会在 return depth + 1 处 处理当前节点，这符合后序遍历的 “处理当前节点”。
• 子节点递归：
  • 递归调用 maxDepth(child) 对每个子节点进行处理，直到到达叶子节点为止。
  • 每次递归返回时，都会把当前子节点的深度更新到 depth 变量中。只有当所有子节点都被处理完后，才会计算并返回当前节点的深度。
• 返回当前节点的深度：
  • 当前节点的深度是 depth + 1，即在遍历完所有子节点后才计算当前节点的深度。也就是只有在处理完所有子节点之后，才返回该节点的深度。

二叉树的最小深度

题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。

所以不能直接把求最大深度的代码换成Math.min()直接用

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int mindepth = 0;
        int leftheight = minDepth(root.left);
        int rightheigth = minDepth(root.right);
        if(root.left == null) {
            return 1 + rightheigth;
        }
        if(root.right == null) {
            return 1 + leftheight;
        }
        return 1 + Math.min(leftheight, rightheigth);
    }
}

一定要记得1+ 不然高度没被记录

原文地址：https://blog.csdn.net/2302_81139517/article/details/144376398

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！