树

树的存储

分为顺序存储和链式存储

顺序存储

使用一段连续的空间存储树

有几种顺序存储方法：

• 双亲表示法
• 孩子表示法
• 双亲孩子表示法

三种方法的优缺点：

1.双亲表示法只记录了一个节点的双亲（父节点），因此无法直接获取该节点的子节点。 2.孩子表示法可以直接获取节点有多少孩子，但每个节点孩子数不一致，只能按照树的度（树中节点的最大度）来分配空间，因此容易导致空间浪费。同时也无法直接获取节点的父节点。 3.双亲孩子表示法可以直接获取节点的父节点和子节点，但由于类似于孩子表示法，同样有浪费空间的问题。

链表存储

二叉树

二叉树有哪些遍历方式？

• 前序
• 中序
• 后序
• 层序（顺或逆层序）

遍历的实现：

中序遍历：

1. 中序实际上需要从最左边的叶子节点开始，也就需要先走到最深处，再往回退，栈正好符合这种特点，遍历方式跟DFS类似。

class Solution {
    public List<Integer> inorderTraversal(TreeNode n) {
        List<Integer> r = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        while (!s.empty() || n != null) {
            while (n != null) {
                s.push(n);
                n = n.left;
            }
            n = s.pop();
            r.add(n.val);
            n = n.right;
        }
        return r;
    }
}

AVL

红黑树

java中的实现有treeSet

树的遍历方式

有很多dfs、bfs、回溯相关的题其实本质都是树的遍历，因此熟练掌握树的各种遍历代码会事半功倍。

多叉树的非重复节点遍历：

// 参考lc 40. 组合总和 II

如图：