剑指Offer-栈、队列、链表和树

这是剑指offer 系列四部曲中的第二部：栈、队列、链表和树。第一部关于字符串和数组，第三部是递归、回溯和动态规划，最后一部分在这里。

从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

正向遍历之后，使用的是python 中list的特性， list[::-1] 这样进行输出的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    # += , -= 这个都是同一种类型的
    def printListFromTailToHead(self, listNode):
        # write code here
        arraylist =[]
        head = listNode
        while head != None:
            arraylist += [head.val]
            # 这个在这里等效于 arraylist.append(head.val)
            head = head.next
        return arraylist[::-1]
            

在线编程中很少考察树的结构。所以就不写 main 函数版本了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    // 跟我的想法是一样的，首先遍历一遍，然后翻转，c++ 中的reverse 操作
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        while(head)
        {
            res.push_back(head->val);
            head =head->next;
        }
        return vector<int>(res.rbegin(), res.rend());
    }
};

重建二叉树 (经典，多敲多背诵)

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

Tips: 递归，二叉树的题目大多数都是可以使用递归的思想进行解决，因为二叉树本身结构就是递归定义的。递归优点在于代码量比较少。从先序遍历中找出根节点，从中序遍历中找出左右子树

别怕，手写中如何重建二叉树，在代码中就是如何实现重建二叉树的。首先从前序list 中找到头结点，然后从中序队列中找见对应节点的index，那么前面的就是头结点的左子树，后面的就是右子树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    # 需要理解在前序遍历中是先遍历左子树的，并且中序和前序中左子树的个数是不会变的
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        root = TreeNode(pre[0])
        # 这个index 函数是需要记住的
        index = tin.index(pre[0])
        # 这里也是需要修改的
        # pre 和 tin都是需要空出一个 root.value 的位置，只不过选择空的位置是不一样的
        root.left = self.reConstructBinaryTree(pre[1:index + 1], tin[:index])
        root.right = self.reConstructBinaryTree(pre[index + 1:], tin[index + 1:])

        return root

优化点：快速的在中序表中找见某个数的位置。使用hash 表实现。

时间复杂度是 $O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<int, int> hash;
    vector<int> preorder, inorder;
    
    TreeNode* reConstructBinaryTree(vector<int> _pre,vector<int> _vin) {
        
        preorder =_pre, inorder =_vin;
        // 方便遍历
        for(int i =0; i< inorder.size(); i++) hash[inorder[i]] =i;
        
        return dfs(0, preorder.size() -1, 0, inorder.size() -1);
    }
    TreeNode* dfs(int pl, int pr, int il, int ir)
    {
        if(pl > pr) return nullptr;
        
        auto root =new TreeNode(preorder[pl]);
        
        int k =hash[root->val];
        auto left =dfs(pl +1, pl+k -il,il, k-1); // 中序和前序对于 左子树的表示
        auto right =dfs(pl+k-il+1, pr, k+1, ir);
        root->left =left, root->right =right;
        return root;
            
    }      
    
};

用两个栈实现队列（经典）

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

Tips：在python 中栈等同于使用list 实现。使用两个栈，意味着一个是push_stack 一个是pop_stack，使用两个栈的“后进先出”表示队列的先进先出（push and pop）从语法上讲，if list1 ==[], 那么 list1 ==None, 这两个条件是可以交换判断的。（在list 中）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def __init__(self):
        self.list1 =[]
        self.list2 =[]
        
    def push(self, node):
        # write code here
        self.list1.append(node)
        
    def pop(self):
        # return 
        if not self.list1  and not self.list2 :
            return None
        if self.list2 :
            return self.list2.pop()
        else:
            while self.list1:
                self.list2.append(self.list1.pop())
            return self.list2.pop()

c++ 实现。

···c++ class Solution { // 使用一个辅助栈 cache 进行pop() 的操作 public: void push(int node) {

    stack1.push(node);
}
void copy(stack<int> &a, stack<int> &b)
{
    while(a.size())
    {
        // 从一个栈到另一个栈的转换，这样就实现了 用栈表示队列
        // 访问机制是 先top() 访问，然后是 pop() 进行弹出
        b.push(a.top());
        a.pop();
    }
}

int pop() {
    copy(stack1, cache);
    int res =cache.top();
    
    cache.pop();
    copy(cache, stack1);
    return res;
    
}

private: stack stack1; stack cache; }; ···

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

Tips：两种解法。一种是遍历存储到list 中，空间复杂度是O(N), 另外一种是两个指针p1，p2，距离相差k，当p2 到达链表尾部，p1 就在导数第k 个位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
"""
尝试使用两个指针版本
p1 p2 并且这种 length 在命名上是需要规范的, 并且这种指针操作，最好是拷贝出来进行操作
不管怎么说，还是应该求解出来 length of listNode，这种才是正途
可以使用两个指针，
"""
class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head == None or k <= 0:
            return None
        p1 = head
        p2 = head
        len1 = 0
        while p1:
            len1 += 1
            p1 = p1.next
        if k > len1:
            return None
        p1 = head
        while k:
            p1 = p1.next
            k -= 1
        while p1:
            p1 = p1.next
            p2 = p2.next
        return p2

有两种思路，一种是正向遍历一遍，存储到list 中，然后使用list 性质，返回倒数第k 个结点，这个空间复杂度是 $O(n)$。还有一种思路是遍历一遍得到链表的长度，然后倒数第 k 个结点就是正向数 n-k +1 个结点，再次遍历一遍就可以返回。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* head, unsigned int k) {
        
        int n =0;
        for(auto p =head ; p; p =p->next) n++; //对于复杂的数据类型，直接使用 auto 这种方式进行定义就可以了
        if(k >n) return nullptr; // 这个是一个细节，但是牛客网上没有显示，如果 k 是超过总的长度那么怎么办
        
        auto p =head;
        for(int i =0; i<n-k; i++) p =p->next;
        return p;
    }
};

** 反转链表**

输入一个链表，反转链表后，输出新链表的表头。

Tips：需要三个指针，cur，next_node, pre。

简单的链表的修改，最后新的表头就是一开始的尾节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


    # -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    """
    修改链表是需要三个指针的 pre, cur, next_node 
    如果对三个指针名进行命名好了，那么这个就是成功的一般了， 这个不容易想到的是
    设置pre =None ，这个是一个细节经验性的问题
    """
    class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            if pHead ==None:
                return None
                
            pre =None
            cur =pHead
            
            while cur:
                next_node =cur.next
                cur.next =pre
                
                pre, cur =cur, next_node
            return pre

单链表中需要记录一个前驱结点。这个是考点所在。这个是没有问题的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        // 这个auto 的关键字 不能是在程序未知的情况下使用，应该是在“可知”的情况下使用
        ListNode* pre =nullptr;
        
        auto cur =head;
        while(cur)
        {
            auto next =cur->next;
            
            cur->next =pre;
            pre =cur;
            // 这个时候需要遍历 cur 指针
            cur =next;
        }
        return pre;
    }
};

合并两个排序的链表

Tips：归并排序中的“并” 操作，只不过由原来的list 操作到现在的 linkedlist 操作。

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


# def __init__(self, x):
#     self.val = x
#     self.next = None

"""
就是在使用两个或者多个 index (p1 or p2) 遍历的时候，一个常见的错误就是忘记了不断更新index
"""

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        head = ListNode(-1)
        head1 = head
        p1 = pHead1
        p2 = pHead2
        while p1 and p2:
            if p1.val < p2.val:
                head.next = p1
                p1 = p1.next
            else:
                head.next = p2
                p2 = p2.next
            head = head.next
        if p1 == None:
            head.next = p2
        if p2 == None:
            head.next = p1
        return head1.next

归并排序的原理，合并两个有序的数组或者链表，使用线性的复杂度就可以使用。

归并排序中while 中使用的if else，然后两个while 判断边界条件。快排中 while 循环里面嵌套的是两个while 排序。这两个排序算法应该是碎觉都是十分熟悉的，怎么可以这样呢？每天都是要多复习的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* p1, ListNode* p2)
    {
        auto dummy =new ListNode(-1); // 虚拟结点
        auto cur =dummy;
        
        while(p1 && p2)
        {
            if(p1->val < p2-> val) 
            {
                cur -> next= p1;
                cur =cur->next;
                p1 =p1->next;
            }
            else
            {
                cur -> next =p2;
                cur =cur->next;
                p2 =p2->next;
            }
        }
        if (p1) cur->next =p1;
        else cur->next =p2;
        return dummy->next;
    }
};

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

递归定义，根节点是否相同，左右子树是否相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


    # -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    """
    分成两部：首先寻找两个根节点的值是否相同；然后判断子树是否完全相同
    subTree 这个函数就是判断子树是否完全相同的，所以函数的功能一定要搞好
    """
    class Solution:
        def HasSubtree(self, pRoot1, pRoot2):
            
            if not pRoot1:
                return False
            if not pRoot2:
                return False
            result =False
            
            if pRoot1.val ==pRoot2.val:
                result =self.subTree(pRoot1, pRoot2)
            if result ==False:
                result = self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
            return result
        
        def subTree(self, root1, root2):
            if not root2:
                return True
            if not root1:
                return False
            if root1.val ==root2.val:
                return self.subTree(root1.left, root2.left) and self.subTree(root1.right, root2.right)
            return False

从字符串的匹配扩展了树的匹配

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* root1, TreeNode* root2)
    {
        if ( !root1 || !root2 ) return false;
        // 这个是寻找根节点的过程
        if(isPart(root1, root2)) return true;
        return HasSubtree(root1-> left, root2) || HasSubtree(root1-> right, root2);
    }
    
    bool isPart(TreeNode *p1, TreeNode *p2)
    {
        // 找到一个根节点相同，然后不断往下遍历的过程
        if (!p2) return true;
        if(!p1 || p1->val != p2-> val) return false;
        return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
    }
};


// 先是遍历找相同的根节点，
// 如果相同的话，接着去找相应的左右子树是否相同

第二遍

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    //先是遍历根节点，然后再遍历对应根节点的左右结点
    bool HasSubtree(TreeNode* root1, TreeNode* root2)
    {
        if( !root1 || ! root2) return false;
        
        if(isSub(root1, root2)) return true;
        
        return HasSubtree(root1-> left, root2) || HasSubtree(root1-> right, root2);
    }
    
    bool isSub(TreeNode * root1, TreeNode * root2)
    {
        if( !root2) return true;
        if( ! root1 || root1->val != root2->val) return false;
        
        return isSub(root1-> left, root2-> left) && isSub(root1-> right, root2-> right);
    }
};

二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

Tips：求解二叉树镜像，A 的左子树对应着B 的右子树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


    # -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    """
    就是在某个左（右）子树是None 的情况下，这个也是可以进行交换的，结束的标志应该是根节点是否为空
    """
    class Solution:
        # 返回镜像树的根节点
        def Mirror(self, root):
            # write code here
            if not root:
                return None
            root.left , root.right =root.right, root.left
            if root.left:
                self.Mirror(root.left)
            if root.right:
                self.Mirror(root.right)
            return root
            

任意一个结点的左右子树都发生互换。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    // 特点，任意一个结点，左右子树都是相反的
    // 互换的过程应该是 从下到上进行的，所以是不断的进行递归，然后最后一个是 swap() 操作
    void Mirror(TreeNode *pRoot) {
        if ( ! pRoot) return ;
        Mirror(pRoot -> left);
        Mirror(pRoot -> right);
        swap(pRoot -> left, pRoot-> right);
        
        
    }
};

包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

Tips: 这个跟“使用两个栈表示队列” 是差不多的，就是单独使用一个list 存储min 函数调用的一个列表，这样的话能达到时间复杂度是 O(1).

在原来的基础上，stack 的基础上，使用新的 min_stack 满足这个需求，同样，原来的 push pop 这种操作还是不能少的。所以是维护了两个 list（normal_list, min_list），但是当normal_list pop() 出来的时候，这个min_list 和其pop 出来的不一定是相同的值。（我感觉）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


# -*- coding:utf-8 -*-
"""
这个栈中最小的元素是变化的，好好理解一下，如果弹出了一个比较大的元素，那么栈中最小的元素是不变的
所含元素的最小元素
top() and min() 操作是不需要删除元素的， pop 是删除了元素

"""
class Solution:
    def __init__(self):
        self.all_list = []
        self.min_list = []

    def push(self, node):
        # write code here
        if not self.min_list:
            self.min_list.append(node)
        else:
            self.min_list.append(min(node, self.min())) # 好多思想都是基于之前的结果进行求解
        self.all_list.append(node)

    def pop(self):
        self.all_list.pop()
        self.min_list.pop()

        # write code here

    def top(self):
        return self.all_list[-1]
        # write code here

    def min(self):
        return self.min_list[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    
    // 关键在于维护两个 stack
    stack<int> stk, stk_min;
    
    // 这个是最重要的function了
    void push(int value) {
        stk.push(value);
        //if( stk_min.size()) value = value< stk_min.top() ? value, stk_min.top();
        if(stk_min.size()) value =std::min(value, stk_min.top());
        stk_min.push(value);
    }
    void pop() {
        stk.pop();
        stk_min.pop();
            
    }
    int top() {
        return stk.top();
        
    }
    int min() {
        return stk_min.top();
    }
};

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

Tips: 使用一个list 来模拟压入和弹出过程，遍历弹出序列popV，如果结束，那么return True。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


def IsPopOrder( pushV, popV):
    if not pushV:
        return False
    tmp =[]
    while popV:
        if tmp and popV[0] == tmp[-1]:
            popV.pop(0)
            tmp.pop()
        elif pushV:
            tmp.append(pushV.pop(0))
        else:
            return False
    return True

是一种模拟题，因为选择是唯一的，对应某种情况，那么操作是一定的。使用一个栈模拟整个操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include<iostream>
#include<vector>
#include<stack>
using namespace std;

bool isPopOrder(vector<int> pushV, vector<int> popV)
{
    if(pushV.size() != popV.size()) return  false;
    stack<int> stk;
    int i =0;
    for(auto u: pushV)
    {
        stk.push(u);
        while(stk.size() && stk.top() == popV[i])
        {
            //cout<< stk.top()<<" "<< endl;
            //cout<< stk.top() <<" "<< i<< endl;
            stk.pop();
            i ++;

        }
    }
    return stk.empty();
}
int main()
{
    vector<int> pushV={1, 2, 3, 4, 5};
    vector<int> popV={4, 5, 3, 2, 1};
    cout<< isPopOrder(pushV, popV)<< endl;
    return 0;
}

从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

Tips：层次遍历，遍历根节点之后加入左右结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    # 层序遍历二叉树， 这个跟数据结构 队列有类似的
    # nodes 装上结点，然后vlaues 装上数值
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        nodes =[]
        values = []
        nodes.append(root)
        while nodes:
            node = nodes.pop(0)
            values.append(node.val)
            if node.left:
                nodes.append(node.left)
            if node.right:
                nodes.append(node.right)
        return values

好的方法，就是枚举出来的方法，大家都是这个是经典的算法，但是这种一开始的 intuition，这种 idea 是怎么出来的。一般是没有人去怎么描述的。所以，是要追根溯源的。对于一个问题，一共有哪些方法是在这个范畴，哪些是可以用的。排除一个认为不可能的，然后就开始尝试。

题目要求是一种层序遍历。对于树的遍历是有深搜和宽搜两种方式，发现神搜不合适，宽搜正好，所以使用宽度优先搜索。对于宽度优先搜索是需要维护一个队列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    // 队列中的操作 queue, front() 访问， pop() 删除
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        
        vector<int> res;
        if( !root) return res;
        
        queue<TreeNode*> qu;
        qu.push(root); 
        while(qu.size())
        {
            auto t =qu.front();
            qu.pop();
            
            res.push_back(t->val);
            if(t->left) qu.push(t->left);
            if(t->right) qu.push(t->right);
        }
        return res;

    }
};

层序遍历，把二叉树打印成多行（这个是输出是多行，而不是一行） c++ 实现。重点使用了 nullptr 指针进行了尾部的标记。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    // 打印成多行，所以在每行打印的时候，每行的最后可以加入一个 nullptr 作为结束
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> res;
            if(! pRoot) return res;
            queue<TreeNode*> qu;
            qu.push(pRoot);
            qu.push(nullptr);
            vector<int> level;
            //判断 queue 是否为空的条件
            while(qu.size())
            {
                auto t =qu.front();
                qu.pop();
                if(! t)
                {
                    if(level.empty()) break;
                    res.push_back(level);
                    qu.push(nullptr);
                    level.clear();
                    continue;
                }
                level.push_back(t->val);
                if(t->left) qu.push(t->left);
                if(t->right) qu.push(t->right);
            }
            return res;
        }
    
};

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

Tips：二叉搜索树，按照中序遍历的话，就是一个排序的二叉树，根节点大于左子树，右子树大于根节点。后序遍历序列中最后一个是根节点，小于根节点是左子树，大于根节点的是右子树，这样进行判断。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    # 后序遍历结果， 最后一个是根节点，这个是递归的思想
    # 二叉搜索树， 左子树小于根节点，右子树大于根节点
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        root = sequence[-1]
        for i in range(len(sequence)):
            if sequence[i] > root:
                break
        for j in range(i, len(sequence)):
            if sequence[j] < root:
                return False
        return True

这个边界条件也是比较好进行处理的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    // 是判断题，需要返回的true or false 两种选择 
    //  搜索二叉树 ，左子树小于根节点， 右子树大于根节点，后序遍历是左子树 右子树 然后是根节点
    // 那么最后一个是根节点，如果值小于根节点，那么就是该根结点的左子树；否则是该根节点的右子树，递归的进行判断
    vector<int> seq;
    bool VerifySquenceOfBST(vector<int> sequence) {
        if( sequence.empty()) return false;
        seq =sequence;
        return dfs(0, seq.size() -1);
    }
    
    bool dfs(int l, int r)
    {
        if(l >= r) return true;
        
        int root =seq[r];
        
        int k =l;
        while( k< r && seq[k] < root) k++;
        for(int i =k; i< r ; i++)
            if(seq[i] < root) return false;
        return dfs(l, k -1) && dfs(k, r-1);

    }
};

二叉树中和为某一值的路径**

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

Tips：树的遍历，深度优先算法（dfs）

这个是非常典型的 dfs，是值得掌握的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    # 深度优先 dfs() 这样的一个算法
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        self.target = expectNumber

        paths = []
        self.dfs(root, [root.val], paths)
        return paths


def dfs(self, root, path, paths):
    if not root.left and not root.right and sum(path) == self.target:
        paths.append(path)

    if root.left:
        self.dfs(root.left, path + [root.left.val], paths)
    if root.right:
        self.dfs(root.right, path + [root.right.val], paths)

c++ 写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    // 深度优先的遍历
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(! root) return res ;
        dfs(root, expectNumber); // 使用 sum -val 可以减少一个变量的使用
        return res;
    }
    void dfs(TreeNode * root, int sum)
    {
        if(!root) return ;
        
        sum -= root-> val;
        path.push_back(root-> val);
        
        if( !root-> left && !root-> right && !sum) res.push_back(path);
        
        dfs(root-> left, sum);
        dfs(root-> right, sum);
        path.pop_back(); // 这个是 c++ 中 vector() 的操作 就是pop_back() 是没有其他的参数的
        
    }
};

复杂链表的复制（比较经典的）

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

Tips: 先是在原来的链表上进行了相同结点的copy和next 指针的指向，然后是random 指针的指向，最后是将原始链表和copy 的链表进行分离。

思路，是先复制节点和 next 指针，然后再遍历一遍复制 random 指针。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50


    # -*- coding:utf-8 -*-
    # class RandomListNode:
    #     def __init__(self, x):
    #         self.label = x
    #         self.next = None
    #         self.random = None
    class Solution:
        # 返回 RandomListNode
        # 首先是结点的复制和 next 指针的连接， 然后是random 指针的连接，最后是选择出复制的结点
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return None
        self.clone_nodes(pHead)
        self.connect_nodes(pHead)
        return self.select_nodes(pHead)
    def clone_nodes(self, head):
        if not head:
            return None
        while head:
            cloned = RandomListNode(head.label)
            cloned.next = head.next
            head.next = cloned
            head = cloned.next
    def connect_nodes(self, head):
        if not head:
            return None

        while head:
            cloned = head.next

            if head.random:
                cloned.random = head.random.next
            head = cloned.next
    def select_nodes(self, head):
        if not head:
            return None
        cloned =cloned_head =None
        # 这个if 的作用是为了保存一个 cloned_head的结点，
        # 一定要从这个功能出发
        if head:
            cloned =cloned_head =head.next
            head.next =cloned.next
            head =head.next
        while head:
            cloned.next =head.next
            cloned =cloned.next
            head.next =cloned.next
            head =head.next
        return cloned_head

思路是完全正确的，但是不知道为什么在牛客上，这个case 通过率是0.真的是太难了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    // 分成三步骤，首先是复制结点插入到原来的链表中，然后处理random指针，最后是将链表挑选出来
    RandomListNode* Clone(RandomListNode* pHead)
    {
        // 加入一个node 是需要操作两个指针的
        for( auto p=pHead; p;)
        {
            auto np =new RandomListNode(p->label);
            auto next =p->next;
            p ->next =np;
            np->next =next;
            p =next;
        }
        
        // 处理random指针
        for(auto p =pHead; p; p =p->next->next)
        {
            if(p->random) p->next ->random =p->random->next;
        }
        
        auto dummy =new RandomListNode(-1);
        auto cur =dummy;
        for( auto p =pHead; p;p =p->next->next )
        {
            cur ->next =p->next;
            cur =cur->next;
            //p =p->next;
        }
        return dummy->next;
        
    }
};

二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

Tips：中序遍历二叉搜索树就是一种排序的树的结点，然后树的左右指针可以作为链表中的指向使用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


    # -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 使用的树的结构 表示一种双向链表
        # 二叉搜索树 ，左子树小于根节点，右子树大于根节点
        # 中序遍历得到就是一种排好序的结构
        # 只能调整树中结点指针的指向
        def Convert(self, pRootOfTree):
            # write code here
            if not pRootOfTree:
                return None
            tree = pRootOfTree
            res = []
            self.helper(tree, res)

        for i in range(len(res) - 1):
            res[i].right = res[i + 1]
            res[i + 1].left = res[i]
        # 这个返回值也是比较鬼畜呀， 就是需要这样返回
        return res[0]

    def helper(self, root, res):
        if not root:
            return None
        if root.left:
            self.helper(root.left, res)
        res.append(root)
        if root.right:
            self.helper(root.right, res)

这个代码长度有点多，所以之后再看。讲解链接

两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

Tips：就是一个 m*n 的问题（m，n 分别代表两个链表的长度）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 两个指针指向的是 一个结点，一个内存的两个指向
    # 将可能不同长度的两个链表转换成相同长度的两个链表的比较，使用
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        p1 = pHead1
        p2 = pHead2
        while p1 != p2:
            # 这个p1 只能指向了最后一个结点，但最后一个节点不一定相同
            p1 = pHead2 if not p1 else p1.next
            p2 = pHead1 if not p2 else p2.next
        return p1

该题目有一种比较巧妙的做法，如果一个指针走完之后，指向另一个list 的开头；同理，另一个指针也是可以这样进行操作。如果是可以相遇的，那么一定最后可以相遇，因为走过的路径是一样的长度的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* head1, ListNode* head2) {
        
        auto p1 =head1, p2 =head2;
        while(p1 != p2)
        {
            if(p1) p1 =p1->next;
            else p1 =head2;
            
            if(p2) p2 =p2->next;
            else p2 =head1;
        }
        // 这个时候p1 和p2 已经相等了
        return p1;
        
    }
};

二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

Tips：递归，相比于二叉树的路径，这个只是返回一个数值就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    """
    分别求解 左右子树的深度，然后max(left, right) 这样的操作
    """

    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        left = self.TreeDepth(pRoot.left) + 1
        right = self.TreeDepth(pRoot.right) + 1
        # 这个return 是最后执行一次的，然后上面那个都是不断的在进行递归加深
        # 这个 left right 已经完成了，最后的效果只是 返回 max(left, right) 这样子
        return max(left, right) 

一般二叉树的问题都是可以使用递归求解的，因为树本身就是使用递归进行定义的。思路：如果左右子树不为空，那么就返回左右子树深度 +1。这个就是递归的定义。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* root)
    {
        if(!root) return 0;
        return max(TreeDepth(root -> left), TreeDepth(root-> right)) +1;
    }
};

平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

Tips：左右子树的深度差最大不超过1。两个递归，一个是计算树的深度的递归，一个是判断左右子树是否是平衡二叉树的递归。

对于平衡二叉树的第一反应，应该想到这个是二叉搜索树的一种改进。为了防止出现链表式的二叉搜索树，平衡二叉树限制了左右子树的相差的高度。通过调整左右子树，保持了二叉搜索树的性质。直观上讲不是很偏（没有偏向一边）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


    # -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 递归常见的都会有两个return 跳出条件，一个是异常的条件，一个是正确的返回
        def get_depth(self, root):
            if not root:
                return 0
            left =self.get_depth(root.left)
            right =self.get_depth(root.right)
        
        return max(left, right) +1
        
    def IsBalanced_Solution(self, pRoot):
        
        if not pRoot:
            return True
        
        left =self.get_depth(pRoot.left)
        right =self.get_depth(pRoot.right)
        
        if abs(left-right) >1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
        

在求解树的深度的过程中，判断是否是平衡二叉树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    // 本问题求解的过程中使用到了 求解树的深度代码
    bool ans =true; 
    bool IsBalanced_Solution(TreeNode* pRoot) {
        dfs(pRoot);
        return ans;
    }
    // 求解深度的过程
    int dfs(TreeNode* root)
    {
        if(! root) return 0;
        
        int left =dfs(root->left ), right =dfs(root-> right);
        if(abs(left -right) >1) ans =false;
        return max(left, right) +1;
        
    }
    
};

链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

Tips：两个快慢指针，开指针在环内相遇慢指针。（两个指针一个需要再环外，一个在环内，然后同样的速度走，最后才能相遇）重置快指针到头结点，两个指针相同速度，当再次相遇时候，那就是入口结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


    # -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 现在长个记性吧，在使用next 这样的时候 要先判断这个是不是存在的
        def EntryNodeOfLoop(self, pHead):
            # write code here
            if not pHead or not pHead.next or not pHead.next.next:
                return None
            twoTimes =pHead.next.next
            oneTime =pHead.next
            while twoTimes != oneTime:
                twoTimes =twoTimes.next.next
                oneTime =oneTime.next
            twoTimes =pHead
            while twoTimes != oneTime:
                twoTimes =twoTimes.next
                oneTime =oneTime.next
            return twoTimes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


#include<iostream>
#include<vector>

using namespace std;

// c++ 中 单链表的定义
struct ListNode{
    int val;
    ListNode *next;
    
    ListNode(int x) :val(x), next(NULL){} // 构造函数
    
};

ListNode *entryNodeOfLoop(ListNode *head)
{
    auto i =head, j =head;
    
    while(i && j)
    {
        i =i->next;
        j =j ->next;
        
        if(j ) j= j->next;
        
        if(i ==j)
        {
            i =head;
            while(i != j)
            {
                i =i->next;
                j =j->next;
            }
            return i;
        }
        
    }
    return 0;
    
}

int main()
{
    ListNode *head =new ListNode(-1);
    
    ListNode *p1 =new ListNode(1);
    ListNode *p2 =new ListNode(2);
    ListNode *p3 =new ListNode(3);
    ListNode *p4 =new ListNode(4);
    head ->next =p1, p1->next =p2, p2->next =p3, p3->next =p4;
    p4->next =p1;
    //cout<< head->val<<endl;
    ListNode *p =entryNodeOfLoop(head);
    
    cout<< p->val<<endl;
    
    return 0;
}

删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        head = ListNode(-1)
        head.next = pHead
        curr = pHead
        last = head
        while curr and curr.next:
            # val =curr.val
            # 这个条件比较简单，所以可以放到前面
            if curr.val != curr.next.val:
                curr = curr.next
                last = last.next
            else:
                # 这个条件 curr 还是需要注意一下的
                val = curr.val
                # python 中 condition1 and condition2 这种是有先后顺序的
                # 可能是存在短路现象的， 如果 curr 不成立，那么后面的是不会执行的 
                # 草拟
                while curr and val == curr.val:
                    curr = curr.next
                last.next = curr
        return head.next

凡是可能把头结点删掉的问题，一般来说我们都是会定义一个虚拟头结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


#include<iostream>
#include<vector>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL){}
};
// 这个是排序之后的链表，那么可以把原来的list 看成一段一段， 使用p 和q 两个指针分别指向的两段的开头
// 对于可能删除头结点的，一般使用虚拟结点，简化处理的情况
ListNode * deleteDumplication(ListNode* head)
{
    auto dummy =new ListNode(-1);
    dummy->next =head;
    auto p =dummy;
    while(p->next)
    {
        auto q =p->next;
        while(q && p->next->val == q->val) q =q->next;
        if(p ->next->next == q) p  =p->next;
        else p->next =q;
    }
    return dummy->next;
}

int main()
{
    auto p1 =new ListNode(1);
    auto p2 =new ListNode(2);
    auto p3 =new ListNode(3);
    auto p22 =new ListNode(2);
    auto p33 =new ListNode(3);
    auto  p4 =new ListNode(4);
    p1->next =p2,p2->next =p22, p22->next =p3, p3->next =p33, p33->next =p4;

    auto res =deleteDumplication(p1);
    cout<< res->val<<endl;

    
    return 0;
}

** 在 $O(1)时间删除链表结点$**

给定单向链表的一个节点指针，定义一个函数在 $O(1)$ 时间删除该结点。

题目视频讲解

一般删除一个节点需要知道其前驱结点，但是还有另外一种做法，就是通过下一个结点覆盖到本结点，然后删除下一个结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val =node->next->val;
        node->next =node->next->next;
        
    }
};

二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

Tips：中序遍历的下一个结点，如果存在右节点，那么下一个结点是右节点最左边的一个点；如果该结点是其父节点的左结点，那么下一节点是其父节点，否则一直回溯。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    # https://blog.csdn.net/fuxuemingzhu/article/details/79723819 
    # 这个是求解中序遍历中某个结点的下一个结点
    # 这pNode 就是一个普通的结点
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        # 如果存在右结点
        if pNode.right:
            pNode = pNode.right
            while pNode.left:
                pNode = pNode.left
            return pNode
        # 如果是父节点的左子树
        else:
            # 这里使用 pNode.next 表示父节点
            while pNode.next:
                if pNode == pNode.next.left:
                    return pNode.next
                # 这个是右结点
                pNode = pNode.next
        return None

对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

Tips: 判断镜像和递归生成进行还是不太一样的哈。递归判断，根节点相同，然后左右子树是否是对称。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:

    # 镜像的概念 和递归
    # isSame() 这个就是判断两个子树是否镜像的操作
    
    def isSame(self, p, q):
        if not p and not q:
            return True
        # 好好思考 下面这两个跳出条件为什么是不合适的
        if p and q and p.val == q.val:
            return self.isSame(p.left, q.right) and self.isSame(p.right, q.left)
    
    
    def isSymmetrical(self, pRoot):
        # write code here
        # 最开始的条件 如果都是 none 那么这个是对称的
        if not pRoot:
            return True
        if pRoot.left and not pRoot.right:
            return False
        if not pRoot.left and pRoot.right:
            return False
        return self.isSame(pRoot.left, pRoot.right)

除了根结点，左右两个子树都是对称的。对称二叉树，非对称二叉树（权值不对称），非对称二叉树（结构不对称）。所以这个是对称或者镜像是有两个维度的，结构和内容。

c++ 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* root)
    {
        if(!root) return true;
        return dfs(root->left, root->right);
    }
    // 在定义的时候，不要使用auto 了，使用具体的类型
    bool dfs(TreeNode *p, TreeNode *q)
    {
        // 如果有空的情况下，只有两者都为空，那么返回的是true，否则是false
        // 这种简洁的代码 就应该记住
        if(!p || !q) return !p && !q;
        
        if(p->val != q->val) return false;
        return dfs(p->left, q-> right) && dfs(p->right, q->left);
        
    }

};

按之字形顺序打印二叉树

对于二叉树的层序遍历有三种不同的题型。

不分行的层序遍历
不分行的层序遍历（偶数行是从左到右，奇数行是从右到左）
分行的层序遍历（每打印一行就另起一行）

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

Tips：层序遍历的升级版，有两种思路，一种是使用单独 stack (list) 的思想存储偶数层数，一种是先按照原先层序遍历的思想，最后对于偶数的结果进行“翻转” 处理。选择后者，因为代码上比较简单。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 层序遍历 + 偶数翻转
    # https://blog.csdn.net/fuxuemingzhu/article/details/79724959
    def level(self, root, level, res):
        """
        root: the root of tree
        level: 
        res: result
        """

        if not root:
            return

        if len(res) == level:
            res.append([])

        res[level].append(root.val)

        if root.left:
            self.level(root.left, level + 1, res)
        if root.right:
            self.level(root.right, level + 1, res)

    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        self.level(pRoot, 0, res)
        for level in range(1, len(res), 2):
            res[level] = res[level][::-1]
        return res

按照之字形顺序打印二叉树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


/*
 struct TreeNode {
 int val;
 struct TreeNode *left;
 struct TreeNode *right;
 TreeNode(int x) :
 val(x), left(NULL), right(NULL) {
 }
 };
 */
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        
        
        vector<vector<int>> res;
        if(! pRoot) return res;
        queue<TreeNode*> qu;
        qu.push(pRoot);
        qu.push(nullptr);
        vector<int> level;
        bool zigzag =false;
        //判断 queue 是否为空的条件
        while(qu.size())
        {
            auto t =qu.front();
            qu.pop();
            if(! t)
            {
                if(level.empty()) break;
                if(zigzag) reverse(level.begin(), level.end());
                res.push_back(level);
                qu.push(nullptr);
                zigzag =!zigzag; // 这个取反的操作
                level.clear(); //因为使用的是push back 操作，所以得clear() 操作
                continue;
            }
            level.push_back(t->val);
            if(t->left) qu.push(t->left);
            if(t->right) qu.push(t->right);
        }
        return res;
    }
};

把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

Tips: 和上一个题目类似，在遍历二叉树的时候，关键是加入了 [level] 层数这种信息。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def level(self, root, level, res):
        # 你这里也没有说要返回值的意思呀，这个直接是 return
        if not root:
            return
        if level == len(res):
            res.append([])

        res[level].append(root.val)
    
        if root.left:
            self.level(root.left, level + 1, res)
        if root.right:
            # res[level] =self.level(root.right, level+1, res)
            # 因为这个是 传的值，所以不需要使用返回值的
            self.level(root.right, level + 1, res)

    def Print(self, pRoot):
        if not pRoot:
            return []
        res = []
        self.level(pRoot, 0, res)
        return res

Binary Tree Right Side View

是层序遍历，核心是理解使用 nullptr 作为一层结束的标志，所以当弹出的是nullptr 的时候，就应该去处理一层的遍历结果，不管是reverse 还是只是取最后一个。并且这个时候是需要加上一个nullptr，表示当前层的结束。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector < int > res;
        if (!root)
            return res;
        queue < TreeNode* > q;
        q.push(root);
        q.push(nullptr);
        vector < int > level;
        while (q.size())
        {
            auto t = q.front();
            q.pop();
            // 因为这里使用 nullptr 作为一层的结束，所以当前的t 为空的时候，最重要的是将 level.back() 加到 res中，然后加上 nullptr
            // 否则的话是不断地 push
            if (!t)
            {
                if (level.empty())
                    break;
                res.emplace_back(level.back());
                q.push(nullptr);
                level.clear();
                continue;
            }
            level.emplace_back(t->val);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }
        return res;
        
    }
};

序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

Tips：序列号和反序列化只是一种约定的存储的形式。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    """
    序列化就是从树结构 转成字符串的结构；反之，也是成立的。 使用先序遍历的方法。
    https://suixinblog.cn/2019/03/target-offer-serialize-binary-tree.html#%E4%BB%A3%E7%A0%81
    """
    def __init__(self):
        self.flag = -1
    def Serialize(self, root):
        # write code here
        if not root:
            return "#"
        return str(root.val) + "," + self.Serialize(root.left) + "," + self.Serialize(root.right)
    
    def Deserialize(self, s):
        # write code here
        self.flag += 1
        string = s.split(',')
        if self.flag > len(string):
            return None
        root = None
        if string[self.flag] != '#':
            root = TreeNode(int(string[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root

序列化二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    // 序列化的时候使用 #表示空节点，节点和结点之间使用 ,隔开
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root, res);
        
        return res;
    }
    void dfs_s(TreeNode* root, string & res)
    {
        if(!root)
        {
            res += "#,";
            return ;
        }
        res += to_string(root->val)+',';
        dfs_s(root->left, res);
        dfs_s(root->right, res);
        
    }
    
    

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u =0;
        return dfs_d(data, u);
        
    }

    TreeNode*  dfs_d(string &data, int &u)
    {
        if(data[u] =='#')
        {
            u +=2;
            return NULL;
        }
        
        
        int t =0;
        bool is_minus =false;
        
        while(data[u] !=',')
        {
            if(data[u] =='-') is_minus =true;
            else t =t*10 +data[u] -'0';
            u ++;
        }
        u ++; // 这个本身代表的含义是  data[u] ==','， 注意这种上下文
        
        if(is_minus ) t =-t;
        auto root =new TreeNode(t);
        root-> left =dfs_d(data, u);
        root->right =dfs_d(data, u);
    
        return root;
    }
};

二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

Tips: 二叉搜索树，中序遍历之后有序，然后取第 k 个结点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:

    def middle(self, root, result):
        if not root:
            return
        if root.left:
            self.middle(root.left, result)
        result.append(root)
        if root.right:
            self.middle(root.right, result)
            
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot:
            return
        result = []
        self.middle(pRoot, result)
        if len(result) < k or k < 1:
            return
        return result[k - 1]

时间复杂度是 $O(K)$, 这个是最优的解法了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* res;
    TreeNode* kthNode(TreeNode* root, int k) {
        
        dfs(root, k);
        return res;
        
    }
    // 当你传递唯一的k 的时候，一定要保证操作的是一个数字。
    void dfs(TreeNode* root, int& k)
    {
        if(! root) return ;// 跳出条件
        dfs(root-> left, k);
        
        k --;
        if(!k) res =root;
        
        if(k >0) dfs(root->right, k);

    }
};

文章目录

重建二叉树 (经典， 多敲多背诵)

用两个栈实现队列 （经典）

二叉树中和为某一值的路径**

复杂链表的复制 （比较经典的）

二叉搜索树与双向链表

重建二叉树 (经典，多敲多背诵)

用两个栈实现队列（经典）

复杂链表的复制（比较经典的）