Tree Cases RFC

[azl397985856]

No description provided.

[sguan94]

树的基本画法

LeetCode中树节点的定义如下

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

依照定义，每个树节点内有 left right 两个指针指向其他树节点，和一个 val 存放值。所以可以将一颗 [2,1,3] 的二叉树绘制成下面的形式（ left 和 right 指向 null 时不画）：

代码中可能出现的对树进行的操作

解树相关的题方法大概可以分为两类：递归和迭代。递归涉及栈空间，迭代涉及树上指针的移动。

Case 1: 递归（DFS）

例如使用递归对一颗二叉搜索树进行前序遍历，我们将传入到递归方法中的节点绘制为高亮
最好在画递归过程时把栈也画出来，同时将栈中的节点和路径都加粗，这样相当于将一条路径绘制出来了

    public void traverse(TreeNode cur){
        if(cur == null) return;
        traverse(cur.left);
        System.out.println(cur.val);
        traverse(cur.right);
    }

.
.

Case 2: 迭代

通常不使用递归就会使用迭代。例如 102. 二叉树的层序遍历。层级遍历涉及到使用 Queue，每次从 Queue 中弹出来一个树节点，然后使用这个节点做一些操作。

TreeNode cur = queue.poll();

我们可以画一个 cur 指针指向树中的节点，同时最好把 queue 也画出来

.
.

Case 3: 对树节点的操作

使用递归或迭代对树进行遍历的过程中通常都涉及到对访问的节点进行一些操作。操作无非是四种：增删改查

增

增加节点的操作无外乎new一个节点，然后将节点连到树上（通常是赋值给某个节点的 left 或者 right 指针）。例如 701. 二叉搜索树中的插入操作 我们需要找到新节点应该被插在什么位置（递归或迭代），然后在那个位置新建节点，并建立和父节点之间的连接。插入操作结束后我们再把树画出来就行，例如我们在下面这颗 BST 上插入 0，我们先找到 0 的父节点 1，然后新建一个节点 val = 0，然后把这个节点赋值给 1 的 left：

.
用户的代码可能会有逻辑错误，例如“寻找新节点位置”的逻辑写错了，cur指针的位置没变一直是在指向root节点，那么新增节点的操作就变成了覆盖（0覆盖到1上面）。这种情况直接画出来就行

删

删除节点的操作无外乎将某一个节点的 left 或 right 指针的值改为 null，但将某一个节点删除后，如果这个节点有子节点，我们应该考虑如何处理这些子节点。例如 450. 删除二叉搜索树中的节点，删节点一共三种情况：

1. 删的节点没有子节点
2. 删的节点有一个子节点
3. 删的节点有两个子节点

如果是没有子节点的情况，那非常简单，我们只需要在删除操作结束后把树再画一遍就行

.
如果是有子节点的情况，最理想的绘制方法是先判断这些子节点还有没有用（是不是会被垃圾回收），如果没用了我们就不用画了；但也可能这些子节点之后还会被用到，例如 450 这道题，我们删除掉一个在树中间的节点后还要在该节点下面的子树中选一个节点提上来放在这个空位上
但这个理想的绘制方案实现起来有点难，我们可以暂时先搞一个简单点的方案，就是将节点删除后的情况直接画出来，删完之后有几颗树就画几颗树。例如删除下面树的根节点：

改

改指更改节点中某些变量的值。这个操作可以分为两类：

1. 改基本类型的值，例如改一下 val 的值，之前是5，现在改成 10。这种情况非常简单，直接画就行
   
2. 改引用类型的值，例如改 left 和 right 指针的值，或者例如 116. 填充每个节点的下一个右侧节点指针 中更改每个节点内 next 指针的值。这种情况下我们最好将这个引用在节点中画出来
   

查

查就是到节点中取值，没什么复杂的部分需要画，我们直接按照 Case1 和 Case2 的绘制方法画出现在我们在查看哪个节点就行