社区 › 业界 › hot100之二叉树上

恃液 发表于 2025-6-18 00:11:01

hot100之二叉树上

二叉树的中序队列(094)

先看代码
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      Stack<TreeNode> stack = new Stack<>();

      while (!stack.isEmpty() || root != null){
            if (root != null){
                stack.add(root);
                root = root.left;
            }else {
                TreeNode node = stack.pop();
                res.add(node.val);
                root = node.right;
            }
      }
      return res;
    }
}

[*]分析
通过stack保存二叉树遍历栈, 反序遍历栈节点
二叉树的最大深度(104)

先看代码
class Solution {
    int res = 0;
    public int maxDepth(TreeNode root) {
      if (root == null) return 0;
      int lefDepth = maxDepth(root.left);
      int rigDepth = maxDepth(root.right);

      return Math.max(lefDepth, rigDepth) + 1;
    }
}

[*]分析
递归调用自身

[*]感悟
递归看的真的非常清爽, 写的也很清爽
翻转二叉树(226)

省略
对称二叉树(101)

省略
二叉树直径(543)

先看代码
class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
      maxDepthBinaryTree(root);
      return res;
    }

    private int maxDepthBinaryTree(TreeNode node){
      if (node == null) return 0;
      int lefMax = maxDepthBinaryTree(node.left);
      int rigMax = maxDepthBinaryTree(node.right);
      res = Math.max(lefMax + rigMax, res);
      return Math.max(lefMax, rigMax) + 1;
    }
}

[*]分析
增加了一个全局res 参数用于记录最大长度, 可能算是贪心

[*]感悟
递归要维持一致的变量与传递参数, 单凭借自身的传递参数无法解决问题, 所以引入了res 全局变量
二叉树的层序遍历(102)

先看代码
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> res= new ArrayList<>();
      Deque<TreeNode> queue = new ArrayDeque<>();

      if (root != null) queue.addFirst(root);
      while (!queue.isEmpty()){
            int n = queue.size();
            List<Integer> layer = new ArrayList<>(n);
            for (int i = 0; i < n; i++){
                TreeNode node = queue.removeLast();
                layer.add(node.val);
                if (node.left != null)queue.addFirst(node.left);
                if (node.right != null) queue.addFirst(node.right);
               
            }
            res.add(layer);
      }

      return res;
    }
}

[*]分析
通过双端队列, 左端入新端点, 右端出老端点, 每次for 循环, 一次性遍历完老端点
将有序数组转换为二叉搜索树(108)

略
验证二叉搜索树(098)

先看代码
class Solution {    public boolean isValidBST(TreeNode root) {      return isValidBST(root, null, null);    }    private boolean isValidBST(TreeNode node, Integer max, Integer min){      if (node == null) return true;      int val = node.val;      if (max != null && val >= max) return false;      if (min != null && val

查看完整版本: hot100之二叉树上