Leetcode Java学习记录——树、二叉树、二叉搜索树

常见二维数据结构：树/图

树和图的区别就在于有没有环。

树的定义

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

树的遍历

前序 中序 后序
根节点所在位置

树天生适合递归。

中序遍历代码

前中后序递归遍历要记牢固。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();//注意用ArrayList定义Listinorder(root,res);return res;}void inorder(TreeNode root,List<Integer> list){if(root==null){return;}inorder(root.left,list);list.add(root.val);inorder(root.right,list);}
}

二叉搜索树

即有序二叉树、排序二叉树。
空树属于二叉搜索树
二叉搜索树要满足：

1. 左子树所有节点的值均小于根节点
2. 右子树所有节点的值均大于根节点
3. 有重复性（左右子树也是二叉搜索树）

大多操作均为O（log2n）复杂度。