剑指offer题解 - 树 | I'm Qiancun Huang

本系列为剑指offer刷题笔记，刷题平台为牛客网。

本文主要是树相关题目题解总结。

4 重建二叉树

题目描述

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

解题思路

前序遍历先根节点再左子树最后右子树，第一个元素肯定是根节点，然后在中序遍历中寻找根节点的索引，按照中序遍历的规则：先左子树再根节点最后右子树，根节点前的一定是左子树的中序数组，根节点后的一定是右子树的中序数组。

因此，我们每次都需要在前序遍历中找根结点并创建一个根结点，然后在中序遍历中确定根结点位置，并确定当前根结点的左右子树，然后以同样的方法去构建左右子树。这整个过程是一个递归的过程。

# -*- 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 or len(pre) != len(tin):
            return None
        
        rootval = pre[0]
        index = tin.index(rootval)
        
        root = TreeNode(rootval)
        root.left = self.reConstructBinaryTree(pre[1:index+1], tin[:index])
        root.right = self.reConstructBinaryTree(pre[index+1:], tin[index+1:])
        
        return root

17 树的子结构

题目描述

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

解题思路

如果树1或树2为空时，返回False
在树1中找到和树2一样的根结点R，然后在判断树1中以R为根结点的子树是否与树2有一样的结构。
先以树1 的根结点为起点寻找是否包含树B，如果找不到就以树A的左结点为起点寻找，若还找不到，以树A的右结点为起点寻找，递归进行

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

node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node1.left = node2
node2.right = node3
node3.left = node4
node3.right = node5

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        result = False
        if pRoot1.val == pRoot2.val:
            # 找到根结点相同的结点
            result = self.isSubTree(pRoot1, pRoot2)
        if not result:
            # 没找到，在左子树寻找
            result = self.HasSubtree(pRoot1.left, pRoot2)
        if not result:
            # 还没找到，在右子树寻找
            result = self.HasSubtree(pRoot1.right, pRoot2)
        return result

    def isSubTree(self,tree1, tree2):
        if not tree2:
            return True
        if not tree1:
            return False
        if tree1.val != tree2.val:
            return False
        return self.isSubTree(tree1.left,tree2.left) and self.isSubTree(tree1.right,tree2.right)

if __name__ == '__main__':
    result = Solution().HasSubtree(node1, node3)
    print(result)

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        
        if not pRoot1 or not pRoot2:
            return False
        
        result = False
        if pRoot1.val == pRoot2.val:
            result = self.judge(pRoot1, pRoot2)
        return result or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
    
    def judge(self, pRoot1, pRoot2):
        if not pRoot2:
            return True
        if not pRoot1 or pRoot1.val != pRoot2.val:
            return False
        return self.judge(pRoot1.left, pRoot2.left) and self.judge(pRoot1.right, pRoot2.right)

18 二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:

二叉树的镜像定义：源二叉树 
                8
               /  \
              6   10
             / \  / \
            5  7 9 11
            镜像二叉树
                8
               /  \
              10   6
             / \  / \
            11 9 7  5

解题思路

递归，判断根节点是否为空，为空时，无需交换，不为空时，交换其左右节点。对左右子树进行递归。

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

node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(10)
node4 = TreeNode(5)
node5 = TreeNode(7)
node6 = TreeNode(9)
node7 = TreeNode(11)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # 递归
        if not root:
            return
        temp = root.left
        root.left = root.right
        root.right = temp
        # if root.left:
        self.Mirror(root.left)
        # if root.right:
        self.Mirror(root.right)
        return root


if __name__ == '__main__':
    result = Solution().Mirror(node1)
    print(result)

迭代。使用栈

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回镜像树的根节点
    def Mirror(self, root):
        # write code here
        if not root:
            return None
        
        stack = [root]
        while stack:
            node = stack.pop(0)
            temp = node.left
            node.left = node.right
            node.right = temp
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root

22 从上往下打印二叉树

解题思路

思路:使用队列

因为按层打印的顺序决定应该先打印根结点，所以我们从树的根结点8开始分析。为了接下来能够打印值为8的两个子结点，我们应该遍历该结点时把值为6和10的两个结点保存到一个容器里，现在容器内就有两个结点了。按照从左到右打印的要求，我们先取出为6的结点。打印出值6之后把它的值分别为5和7的两个结点放入数据容器。此时数据容器中有三个结点，值为10,5和7。接下来我们从容器中取出值为10的结点，注意到值为10的结点比值为5,7的结点先放入容器，此时又比这两个结点先取出，同时将9和11放入数据容器，这就是我们通常说的先入先出，因此数据容器为一个队列。由于值为5,7,9,11的结点都没有子结点，因此只要依次打印即可。

通过例子，我们找到从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点，则把该结点的左右结点依次放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直到队列中所有结点都打印出来为止。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(10)
node4 = TreeNode(5)
node5 = TreeNode(7)
node6 = TreeNode(9)
node7 = TreeNode(11)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        ans = []
        if not root:
            return ans
        queue = []
        queue.append(root)
        while queue:
            cur = queue.pop(0)
            ans.append(cur.val)
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)
        return ans

if __name__ == '__main__':
    result = Solution().PrintFromTopToBottom(node1)
    print(result)

递归

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        if not root:
            return []
        
        res = []
        self.level(root, 0, res)
        
        ans = []
        for x in res:
            ans += x
        
        return ans
    
    def level(self, root, level, res):
        if not root:
            return
        if level == len(res):
            res.append([])
        res[level].append(root.val)
        self.level(root.left, level+1, res)
        self.level(root.right, level+1, res)

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

题目描述

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

解题思路

以[5,7,6,9,11,10,8]为例，后序遍历结果的最后一个数字8 就是根结点的值，在这个数组中，前三个数字5、7和6都比8小，是值为8的结点的左子树结点；后三个数字9、11和10都比8大，是值为8的结点的右子树。

用同样的方法确定与数组每一部分对应的子树的结构，这其实就是一个递归的过程，对于序列5,7,6，最后一个数字6是左子树的根结点的值，数字5比6小，是值为6的结点的左子结点，而7则是它的右子结点。同样，在序列9、11、10中，最后一个数字10是右子树的根结点，数字9比10小，是值为10的结点的左子结点，而11则是它的右子结点。

使用递归的方法，先判断数组的左子树和右子树的位置，找出左子树后。判断右子树是不是二叉搜索树。

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if len(sequence) == 0:
            return False
        if len(sequence) <= 2:
            return True
        
        rootval = sequence[-1]
        k = 0
        while k < len(sequence)-1 and sequence[k] < rootval:
            k += 1
        
        for i in range(k, len(sequence)-1):
            if sequence[i] <= rootval:
                return False
            
        left = right = True
        if sequence[:k]:
            left = self.VerifySquenceOfBST(sequence[:k])
        if sequence[k:-1]:
            right = self.VerifySquenceOfBST(sequence[k:-1])
            
        return left and right

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

题目描述

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

解题思路

递归，深度优先搜索，使用前序遍历。
每次遍历，判断当前root是否同时满足：

与给定数值相等
左子树为空
右子树为空

如果满足条件，返回val值。
如果不是叶子结点，我们分别对根结点的左子树右子树进行递归，直到找到叶子结点，然后遍历把叶子结点和父节点对应的val组成的序列返回上一层；如果叶子结点不满足与给定值相等，其实也返回了序列，只不过是空序列。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(10)
node4 = TreeNode(5)
node5 = TreeNode(7)
node6 = TreeNode(9)
node7 = TreeNode(1)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        res = []
        self.dfs(root, expectNumber, [root.val], res)
        return res
    
    def dfs(self, root, expectNumber, path, res):
        if not root:
            return
        if not root.left and not root.right and sum(path) == expectNumber:
            res.append(path)
            return
        if root.left:
            self.dfs(root.left, expectNumber, path+[root.left.val], res)
        if root.right:
            self.dfs(root.right, expectNumber, path+[root.right.val], res)

if __name__ == '__main__':
    result = Solution().FindPath(node1, 19)
    print(result)

26二叉搜索树与双向链表

题目描述

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

解题思路

二叉搜索树如上图所示，我们将其转换为排序双向链表
根据二叉搜索树的特点：左结点的值<根结点的值<右结点的值，我们不难发现，使用二叉树的中序遍历出来的数据的排序，就是排序的顺序。因此，确定了二叉搜索树的遍历方法。
接下来，我们可以把树分成三部分，值为10的结点，根节点为6的左子树，根结点为14的右子树。根据排序双向链表的定义，值为10的结点将和它的左子树的最大一个结点链接起来，同时它还将和右子树最小的结点链接起来。

根据中序遍历的顺序，当我们遍历到根结点时，它的左子树已经转换成一个排序的好的双向链表了，并且处在链表中最后一个的结点是当前值最大的结点。我们把值为8的结点和根结点链接起来，10就成了最后一个结点；接着我们就去遍历右子树，并把根结点和右子树中最小的结点链接起来。最后，设置从最左边的结点开始

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None
node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(14)
node4 = TreeNode(4)
node5 = TreeNode(8)
node6 = TreeNode(12)
node7 = TreeNode(16)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree or (not pRootOfTree.left and not pRootOfTree.right):
            return pRootOfTree
        #处理左子树
        self.Convert(pRootOfTree.left)
        left = pRootOfTree.left
        #左子树最右节点与根节点链接
        if left:
            while left.right:
                left = left.right
            left.right = pRootOfTree
            pRootOfTree.left = left
        #处理右子树
        self.Convert(pRootOfTree.right)
        right = pRootOfTree.right
        #右子树最左节点与根节点链接
        if right:
            while right.left:
                right = right.left
            right.left = pRootOfTree
            pRootOfTree.right = right
        
        while pRootOfTree.left:
            pRootOfTree = pRootOfTree.left
        
        return pRootOfTree

if __name__ == '__main__':
    result = Solution().Convert(node1)

38 二叉树的深度

题目描述

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

解题思路

思路1：递归，结点为空时，返回0

不为0时，遍历左右子树，在较深的子树上加1
思路2：bfs 层次遍历

每遍历完一层，层数加1
q为当前层的结点，遍历q中的每个结点，然后用tmp保存当前每个结点可能有的左结点和右结点。

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None
node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(10)
node4 = TreeNode(5)
node5 = TreeNode(7)
node6 = TreeNode(9)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        # 思路1
        # if not pRoot:
        #     return 0
        # return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1

        # 思路2
        if not pRoot:
            return 0
        count = self.levelOrder(pRoot)
        return count

    def levelOrder(self,pRoot):
        count = 0
        if not pRoot:
            return count
        queue = []
        queue.append(pRoot)
        while queue:
            temp = []
            for i in range(len(queue)):
                r = queue.pop(0)
                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)
                temp.append(r.val)
            if temp:
                count += 1
        return count


if __name__ == '__main__':
    result = Solution().TreeDepth(node1)
    print(result)

39 平衡二叉树

题目描述

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

解题思路

平衡二叉树：它是一棵空树，或者它的两个子树的高度差的绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树。

重复遍历多次：
BST的定义为|height(lefttree)−height(righttree)|<=1，原问题拆分为计算树高度和判断高度差
但是，在遍历每个结点时，调用函数TreeDepth得到它的左右子树的深度，如果每个结点的左右子树的深度相差不超过1，则这是一颗平衡的二叉树。这种方法的缺点是，首先判断根结点是不是平衡的，需要使用TreeDepth获得左右子树的深度，然后还需要继续判断子树是不是平衡的，还是需要使用TreeDepth获得子树的左右子树的深度，这导致了大量的重复遍历。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        
        if abs(self.depth(pRoot.left) - self.depth(pRoot.right)) <= 1:
            return True
        
        return False
    
    def depth(self, pRoot):
        if not pRoot:
            return 0
        
        return max(self.depth(pRoot.left), self.depth(pRoot.right)) + 1

57 二叉树的下一个结点

题目描述

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

解题思路

三种情况

当前结点有右子树。当前结点的下一结点是右子树中的最左子结点，如node=8，它的下一结点为12.
当前结点无右子树，且当前结点是其父结点的左孩子。下一结点为当前结点的父结点，如node=8，它的下一个结点为12。
当前结点无右子树，且当前结点是其父结点的右孩子。则一直向上遍历，直到找到最靠近的一个祖先节点pNode且pNode是其父节点的左子节点，那么输入节点的下一个结点就是pNode的父节点。如node=14，它的下一个结点为16.

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    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
        if pNode.next and pNode == pNode.next.left:
            return pNode.next
        if pNode.next and pNode == pNode.next.right:
            pNode = pNode.next
            while pNode.next and pNode == pNode.next.right:
                pNode = pNode.next
            return pNode.next
        
        return None

58 对称的二叉树

题目描述

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

解题思路

判断一棵二叉树是不是对称的，等价于判断其左右子树是不是镜像对称的。判断镜像对称即判断对称位置上的元素是不是相等的。
两个结点AB对称等价于：

两个结点值相等
结点A的左子树和结点B的右子树对称
结点A的右子树和结点B的左子树对称

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        
        return self.judge(pRoot.left, pRoot.right)
    
    def judge(self, pRoot1, pRoot2):
        if not pRoot1 and not pRoot2:
            return True
        if not pRoot1 or not pRoot2:
            return False
        if pRoot1.val != pRoot2.val:
            return False
        return self.judge(pRoot1.left,pRoot2.right) and self.judge(pRoot1.right,pRoot2.left)

59 按之字顺序打印二叉树

题目描述

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

解题思路

层次遍历保存结点，最后奇数层翻转

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node1.left = node2
node1.right = node3
node2.left = node4
node3.right = node5
class Solution:
    def Print(self, pRoot):
        # write code here
        # 层次遍历保存结点，最后奇数层翻转
        ans = []
        if not pRoot:
            return ans
        queue = []
        queue.append(pRoot)
        while queue:
            temp = []
            for i in range(len(queue)):
                r = queue.pop(0)
                temp.append(r.val)
                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)
            ans.append(temp)
        for i in range(1,len(ans),2):
            ans[i] = ans[i][::-1]
        return ans

if __name__ == '__main__':
    # [[1] [3 2] [4 5]]
    result = Solution().Print(node1)
    print(result)

递归

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        
        res = []
        self.level(pRoot, 0, res)
        
        for i in range(1, len(res), 2):
            res[i] = res[i][::-1]
        
        return res
    
    def level(self, pRoot, level, res):
        if not pRoot:
            return
        if level == len(res):
            res.append([])
        res[level].append(pRoot.val)
        self.level(pRoot.left, level+1, res)
        self.level(pRoot.right, level+1, res)

60 把二叉树打印成多行

题目描述

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

解题思路

比上题简单，直接层次遍历

# -*- 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 Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        stack = [pRoot]
        while stack:
            temp = []
            for i in range(len(stack)):
                node = stack.pop(0)
                temp.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
            res.append(temp)
        
        return res

递归

# -*- 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 Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res = []
        self.level(pRoot, 0, res)
        return res
    
    def level(self, pRoot, level, res):
        if not pRoot:
            return
        if level == len(res):
            res.append([])
        res[level].append(pRoot.val)
        self.level(pRoot.left, level+1, res)
        self.level(pRoot.right, level+1, res)

61 序列化二叉树

题目描述

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

解题思路

序列化二叉树：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串。需要注意的是，序列化二叉树的过程中，如果遇到空节点，需要以某种符号（这里用#）表示。以下图二叉树为例，序列化二叉树时，需要将空节点也存入字符串中。

序列化可以基于先序/中序/后序/按层等遍历方式进行，这里采用先序遍历的方式实现，字符串之间用 “，”隔开。

反序列化二叉树：根据某种遍历顺序得到的序列化字符串，重构二叉树。具体思路是按前序遍历“根左右”的顺序，根节点位于其左右子节点的前面，即非空（#）的第一个节点是某子树的根节点，左右子节点在该根节点后，以空节点#为分隔符。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    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
        s = s.split(',')
        return self.Tree(s)
    
    def Tree(self, s):
        if not s:
            return None
        val = s.pop(0)
        root = None
        if val != '#':
            root = TreeNode(int(val))
            root.left = self.Tree(s)
            root.right = self.Tree(s)
        return root

62二叉搜索树的第k个结点

题目描述

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

给定一颗二叉搜索树，请找出其中的第k大的结点。
例如，

               5
              /  \ 
             3    7 
            / \  / \ 
           2  4  6  8 
中，按结点数值大小顺序第三个结点的值为4。

解题思路

思路1:

这棵树是二叉搜索树，首先想到的是二叉搜索树的一个特点：左子结点的值 < 根结点的值 < 右子结点的值。
遇到bst（二叉搜索树）想到中序遍历，先中序遍历，然后找出第k个结点。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot or k <= 0:
            return None
        res = []
        self.inorder(pRoot, res)
        
        return res[k-1] if k <= len(res) else None
    
    def inorder(self, pRoot, res):
        if not pRoot:
            return
        self.inorder(pRoot.left, res)
        res.append(pRoot)
        self.inorder(pRoot.right, res)


 if __name__ == '__main__':
    result = Solution().KthNode(node1,3)
    print(result.val)

思路2. 先将全部左子树入栈，然后依次出栈，出栈过程中，如果右子树存在，则将其全部左子树入栈。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot or k <= 0:
            return None
        res = []
        stack = []
        self.allLeftinStack(pRoot, stack)
        
        while stack:
            node = stack.pop()
            res.append(node)
            if node.right:
                self.allLeftinStack(node.right, stack)

        return res[k-1] if k <= len(res) else None
    
    def allLeftinStack(self, root, stack):
        while root:
            stack.append(root)
            root = root.left

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot or k <= 0:
            return None
        res = []
        stack = [pRoot]
        while pRoot.left:
            stack.append(pRoot.left)
            pRoot = pRoot.left
        
        while stack:
            node = stack.pop()
            res.append(node)
            if node.right:
                stack.append(node.right)
                temp = node.right
                while temp.left:
                    stack.append(temp.left)
                    temp = temp.left

        return res[k-1] if k <= len(res) else None