1、二叉树前中后序遍历:https://blog.csdn.net/cm15835106905/article/details/124699173
2、输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
public class Solution {private TreeNode prev = null; // 用于记录链表的前一个节点private TreeNode head = null; // 头节点public TreeNode convertToDoublyLinkedList(TreeNode root) {if (root == null) {return null;}inOrderConvert(root);return head;}private void inOrderConvert(TreeNode node) {if (node == null) {return;}// 递归遍历左子树inOrderConvert(node.left);// 将当前节点链接到前一个节点if (prev == null) {// 当前节点是最左节点,赋值为头节点head = node;} else {// 将前一个节点的right指向当前节点prev.right = node;// 当前节点的left指向前一个节点node.left = prev;}// 更新前一个节点为当前节点prev = node;// 递归遍历右子树inOrderConvert(node.right);}public static void main(String[] args) {TreeNode root = new TreeNode(10);root.left = new TreeNode(6);root.right = new TreeNode(14);root.left.left = new TreeNode(4);root.left.right = new TreeNode(8);root.right.left = new TreeNode(12);root.right.right = new TreeNode(16);Solution solution = new Solution();TreeNode head = solution.convertToDoublyLinkedList(root);// 打印双向链表while (head != null) {System.out.print(head.val + " ");head = head.right;}}
}
解释:
变量定义:
prev 用于记录当前节点的前一个节点。
head 用于记录转换后的双向链表的头节点。
中序遍历: 使用递归的方式遍历二叉搜索树。对于每个节点:
递归遍历左子树。
处理当前节点,将 prev 节点的 right 指针指向当前节点,当前节点的 left 指针指向 prev 节点。
更新 prev 节点为当前节点。
递归遍历右子树。
输出双向链表:
转换完成后,我们可以遍历链表进行输出,验证结果是否正确。
3、二叉树深度
4、