leetcode总结无止境系列之树

遇到树的问题,首先要弄清楚是什么样的树,不要先入为主一定是二叉树,再就是有没有带特殊性质,比如说有序二叉树、平衡二叉树等等。 树的题目主要有以下几种:

一. 树的遍历。前序、中序、后序、层序(借助"先进先出"的队列),如果直接考遍历,一般是让你写非递归代码的(通过栈模拟)(递归版较简单);另一个就是给个中序+前序(后序),还原二叉树,其中中序必须给,解不唯一,一般用递归解决;还有判断一个二叉树是否对称/互为镜像?(中序遍历为回文串)

二. BST(Binary Search Tree)。怎么判断是不是BST(或者平衡树,或者完全树);有序数组(有序链表)转换成BST;在BST中找某个upper_bound的最大值(这个可以给root让你找符合要求的节点,可以给一个等于upper_bound的节点,有parent指针,让你找);

三. LCA(Least Common Ancestor,最近公共祖先)。超高频题,主要考法是给两个指针和树的root,找LCA,如果节点有parent节点(这时候就不给root了),就相当于链表找第一个交点了,如果没有parent就要麻烦一点;

四. 在二叉树中找出和为某一值的所有路径。涉及到BFS、DFS。

五. 序列化与反序列化。写一个序列化和反序列化的方法。一般思路是加一个不会出现的字符作为分割。有时候会说任何字符都可能出现,这时候可以用转义字符。

序列化:为了能够在重构二叉树时结点能够插入到正确的位置,在使用先序遍历保存二叉树到文件中的时候需要把NULL结点也保存起来(可以使用特殊符号如"#"来标识NULL结点)。 假定二叉树如下所示:

30

10 20

50 45 35

则使用先序遍历,保存到文件中的内容如下: 30 10 50 # # # 20 45 # # 35 # #

void writeBinaryTree(BinaryTree *p, ostream &out) //BinaryTree是二叉树结构体
{
    if (!p) {
    out << "# ";
    } else {
    out << p->data << " ";
            writeBinaryTree(p->left, out);
    writeBinaryTree(p->right, out);
    }
}

反序列化:从文件中读取二叉树结点并重构的方法与前面相似。采用先序遍历的思想每次读取一个结点,如果读取到NULL结点的标识符号"#";,则忽略它。如果读取到结点数值,则插入到当前结点,然后遍历左孩子和右孩子。

void readBinaryTree(BinaryTree *&p, ifstream &fin)
{
    int token;
    bool isNumber;
    //readNextToken读取文件下一个值,如果是数字返回true,否则返回false
    if (!readNextToken(token, fin, isNumber))           return;
    if (isNumber) {
        p = new ListNode(token);
        readBinaryTree(p->left, fin);
        readBinaryTree(p->right, fin);
    }
}

ps:除了先序遍历,其实还可以使用层序遍历来序列化二叉树。此外,本文采用先序遍历保存NULL结点的方法存在缺陷,因为这样二叉树结点不能保存标识符。如本方法中二叉树结点值就不能是“#”。如果要能保存各种字符,则需要采用其他方法来实现了。不管怎样,对于面试来讲,这样的解法已经可以过关了。

leetcode 上相关题目汇总

//Definition for binary tree
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

1.Balanced Binary Tree

2.Symmetric Tree

3.Same Tree

4.Validate Binary Search Tree

5.Recover Binary Search Tree

6.Binary Tree Inorder Traversal

7.Binary Tree Level Order Traversal

8.Binary Tree Level Order Traversal II

9.Binary Tree Zigzag Level Order Traversal

10.Maximum Depth of Binary Tree

11.Minimum Depth of Binary Tree

12.Construct Binary Tree from Preorder and Inorder Traversal

13.Construct Binary Tree from Inorder and Postorder Traversal

14.Convert Sorted Array to Binary Search Tree

15.Convert Sorted List to Binary Search Tree

16.Flatten Binary Tree to Linked List

crystal /
Published under (CC) BY-NC-SA in categories 面试  tagged with leetcode  数据结构