树

• 树和图的区别就是没有环
• 链表就是特殊的树
• 树就是特殊的图

二叉树

二叉搜索树

• 又称二叉搜索排序树，排序二叉树，是指一棵空树或者具有下列性质的二叉树
  • 左子树上所有节点的值均小于根节点的值
  • 右子树上所有节点的值均大于根节点的值
  • 以此类推，左右子树也分别为二叉搜索树，这就是重复性
• 中序遍历是升序排列
• 查询、创建、删除的时间复杂度都是 O(log n) ，虽然比链表的创建 O(1)慢，但整体效率高 ，高过查询的O(n)

• 树的面试题的解法一般都是递归

  • 树本身的定义没有便于循环的结构，更多的是左右子节点
  • 访问左右子节点最方便的就是调用相同的遍历函数

    实战

    讲解

• https://leetcode.cn/problems/binary-tree-inorder-traversal/

  练习

• https://leetcode.cn/problems/binary-tree-preorder-traversal/

• https://leetcode.cn/problems/n-ary-tree-postorder-traversal/
• https://leetcode.cn/problems/n-ary-tree-preorder-traversal/
• https://leetcode.cn/problems/n-ary-tree-level-order-traversal/