树、二叉树、二叉搜索树的实现和特性

回顾

单链表Linked List

查询 O(n)时间复杂度

如果要加速，关键在于升维

树

树和图（Graph）最关键的差别在于有没有环

有环就成了图

特殊情况下可以这样理解：

• ? Linked List是特殊化的树

• ? Tree是特殊化的Graph

示例代码

Java

public class TreeNode {
	public int val;
	public TreeNode left, right;
	public TreeNode(int val){
		this.val = val;
		this.left = null;
		this.right = null;
	}
}

C++

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x):val(x), left(NULL), right(NULL){}
}

Python

class TreeNode
	def _init_(self, val):
    self.val = val
    self.left, self.right = None, None

为什么会出现树

二叉树遍历 Pre-order/In-order/Post-order

1. 前序（Pre-order）：根-左-右
2. 中序（In-order）：左-根-右
3. 后序（Post-order）：左-右-根

前中后序遍历 示例代码

def preorder(self, root):
  if root:
    self.traverse_path append(root.val)
    self.preorder(root.left)
    self.preorder(root.right)
    

def inorder(self, root):
  if root:
    self.inorder(root.left)
    self.traverse_path.append(root.val)
    self.inorder(root.right)
    
    
def postorder(self, root):
  if root:
    self.postorder(root.left)
    self.postorder(root.right)
    self.traverse_path.append(root.val)

二叉搜索树Binary Search Tree

例题：二叉树的中序遍历 LeetCode94

给定一个二叉树，返回它的中序遍历

示例：

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

class Solution {
  public List inorderTraversal(TreeNode root) {
    List res = new ArrayList<>();
    helper(root, res);
    return res;
  }
  
  public void helper(TreeNode root, List res) {
    if (root != null) {
      if (root.left != null) {
        helper(root.left, res);
      }
      res.add(root.val);
      if (root.right != null) {
        helper(root.right, res);
      }
    }
  }
}

树 为什么经常使用递归

没有后继的结构

直接对左节点调相应的函数

def inorder(self, root):
  if root:
    self.inorder(root.left)
    self.traverse_path.append(root.val)
    self.inorder(root.right)

class Solution {
  public List ans(List )
}