二叉树详解

先序遍历求和：

• 逆序访问节点，累加值。
• 代码：

  private static void preOrder(TreeNode root) {    if (Objects.isNull(root)) {        return;    }    int sum = root.getValue() + 1;    System.out.println(sum + " ");    preOrder(root.getLeftNode());    preOrder(root.getRightNode());}

判断两棵树是否相同：

• 递归比较节点值和左右子树结构。
• 代码：

  private boolean isSameTree(TreeNode root1, TreeNode root2) {    if (Objects.isNull(root1) && Objects.isNull(root2)) {        return true;    }    if (Objects.isNull(root1) || Objects.isNull(root2)) {        return false;    }    if (root1.getValue() != root2.getValue()) {        return false;    }    return isSameTree(root1.leftNode, root2.leftNode) &&           isSameTree(root1.rightNode, root2.rightNode);}

层序遍历：

• 使用队列按层遍历。
• 代码：

  private static List
        
          levelOrder(TreeNode root) {    List
         
           result = new ArrayList<>();    if (Objects.isNull(root)) {        return result;    }    Queue
          
            queue = new LinkedList<>();    queue.offer(root);    while (!queue.isEmpty()) {        int size = queue.size();        for (int i = 0; i < size; i++) {            TreeNode node = queue.poll();            result.add(node.getValue());            if (node.leftNode != null) {                queue.offer(node.leftNode);            }            if (node.rightNode != null) {                queue.offer(node.rightNode);            }        }    }    return result;}
          
         
        

节点数计算：

• 使用层序遍历统计节点数。
• 代码：

  private static int countNodes(TreeNode root) {    if (Objects.isNull(root)) {        return 0;    }    return 1 + countNodes(root.leftNode) + countNodes(root.rightNode);}

交换左右节点：

• 递归交换每个节点的左右子树。
• 代码：

  public TreeNode invertTree(TreeNode root) {    if (Objects.isNull(root)) {        return null;    }    TreeNode temp = root.rightNode;    root.rightNode = root.leftNode;    root.leftNode = temp;    invertTree(root.leftNode);    invertTree(root.rightNode);    return root;}

完全二叉树节点数：

• 判断是否为完全二叉树，计算满二叉树节点数。
• 代码：

  private static int getPrefectBinaryCount(TreeNode root) {    int height = 0;    while (Objects.nonNull(root)) {        root = root.getLeftNode();        height++;    }    return (int) Math.pow(2, height) - 1;}

序列化：

• 使用前序遍历生成字符串。
• 代码：

  public static String serialize(TreeNode root) {    StringBuilder sb = new StringBuilder();    serialize(root, sb);    return sb.toString();}private static void serialize(TreeNode root, StringBuilder sb) {    if (Objects.isNull(root)) {        sb.append("#,");        return;    }    sb.append(root.getValue() + ",");    serialize(root.leftNode, sb);    serialize(root.rightNode, sb);}

反序列化：

• 使用队列反序读取节点值。
• 代码：

  public static TreeNode deserialize(String data) {    LinkedList
        
          nodes = new LinkedList<>();    for (String s : data.split(",")) {        nodes.addLast(s);    }    return deserialize(nodes);}public static TreeNode deserialize(LinkedList
         
           nodes) {    if (nodes.isEmpty()) {        return null;    }    String first = nodes.removeFirst();    if (first.equals("#")) {        return null;    }    int value = Integer.parseInt(first);    TreeNode root = new TreeNode(value);    root.leftNode = deserialize(nodes);    root.rightNode = deserialize(nodes);    return root;}
         
        

最近公共祖先：

• 使用层序遍历找出p和q的最近公共祖先。
• 代码：

  public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    if (Objects.isNull(root)) {        return null;    }    if (root == p || root == q) {        return root;    }    TreeNode left = lowestCommonAncestor(root.leftNode, p, q);    TreeNode right = lowestCommonAncestor(root.rightNode, p, q);    if (Objects.nonNull(left) && Objects.nonNull(right)) {        return root;    }    if (Objects.isNull(left) && Objects.isNull(right)) {        return null;    }    return Objects.nonNull(left) ? left : right;}

二叉搜索树遍历：

• 递归或迭代地查找目标值。
• 代码：

  public static void binarySearchTree(TreeNode root, int target) {    if (Objects.isNull(root)) {        return;    }    if (root.value == target) {        return;    }    if (root.value < target) {        binarySearchTree(root.rightNode, target);    } else {        binarySearchTree(root.leftNode, target);    }}