Tree

[caipengbo]

树

[caipengbo]

遍历

三种遍历的递归写法

迭代写法

前序

List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
stack.add(cur);
while (!stack.isEmpty()) {
    cur = stack.pop();
    if (cur != null) {
        ret.add(cur.val);
        stack.add(cur.right);
        stack.add(cur.left);
    }
}
return ret;

中序

List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
    while (cur != null) {
        stack.add(cur);
        cur = cur.left;
    }
    cur = stack.pop();
    ret.add(cur.val);
    cur = cur.right;
}
return ret;

后序

前序遍历的顺序是 根-左-右，后序遍历的顺序是 左-右-根 那么 前序稍微修改一下 变成 根-右-左，然后把结果倒序，就变成 左-右-根* 了

// 使用LinkedList的头插，让结果倒序
LinkedList<Integer> ret = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
stack.add(cur);
while (!stack.empty()) {
    cur = stack.pop();
    if (cur != null) {
        ret.addFirst(cur.val);  // 头插法，让结果倒序
        stack.add(cur.left);
        stack.add(cur.right);
    }
}
return ret;

[caipengbo]

根据遍历序列构建树

105 前中(唯一) 106 中后(唯一) 889 前后(不唯一)

[caipengbo]

递归思想

树与其子树

边界：叶子节点 和 空节点

递归中类的成员变量的使用（一种类内全局变量），第297题

递归与自顶向下与自底向上

[caipengbo]

其他

判断两个节点是否同时为空 if (p == null || q == null) return p == q; // 更精简的写法

[caipengbo]

如果面试题要求处理一棵二又树的遍历序列，则可以先找到二叉树的根节点，再基于根节点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。本面试题应用的是这种思路，面试题7“重建二叉树"就是这种思路