二叉树种类

1.二叉树的高度

class TreeNode(object):    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass Solution(object):    def maxHeight(self, root):        if root==None:            return 0        leftheight=self.maxHeight(root.left)        rightheight=self.maxHeight(root.right)        if leftheight>=rightheight:            return leftheight+1        else:            return rightheight+1

2. 分层打印二叉树

class TreeNode:    def __init__(self,x):        self.val  = x        self.left = None        self.right = Noneclass Solution:    def printBinary(self, root):        queue = []        res = []        if root = None:            return []        queue.append(root)        while queue:            newnode = queue.pop(0)            res.append(newnode.val)            if(newnode.left):                queue.append(newnode.left)            if(newnode.right):                queue.append(newnode.right)        return res

class Solution:    # 返回二维列表[[1,2],[4,5]]    def Print(self, pRoot):        # write code here        result = []        nodeList = []        if pRoot == None:            return result        nodeList.append(pRoot)        while nodeList:            result_layer = []            nextLayernodeList = []            for node in nodeList:                result_layer.append(node.val)                if node.left:                    nextLayernodeList.append(node.left)                if node.right:                    nextLayernodeList.append(node.right)            nodeList = nextLayernodeList            result.append(result_layer)        return result

3. 判断是否为平衡二叉树

class TreeNode():    def __init__(self,x):        self.val  = x        self.left = None        self.right = Noneclass Solution:    def getDeepth(self,Root):        if Root is None:            return 0        nright = self.getDeepth(Root.right)        nleft = self.getDeepth(Root.left)        return max(nright,nleft)+1    def IsBalance_solution(self,pRoot):        if pRoot is None:            return True        right = self.getDeepth(pRoot.right)        left = self.getDeepth(pRoot.left)        if abs(right - left) > 1:            return False        return self.IsBalance_solution(pRoot.right) and self.IsBalance_solution(pRoot.left)

 

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

思路：1. 前序遍历首位是根节点，找到根节点之后，根据中序遍历找到左右子树

           2. 把找到的根节点从pre里删除，分别找到1中的左右子树, preleft preright vinleft vinright

　　　3. 然后左右子树带入1中

/* function TreeNode(x) {    this.val = x;    this.left = null;    this.right = null;} */function reConstructBinaryTree(pre, vin){    var result = null;    if(pre.length>1) {        var root= pre[0];        var vinrootindex = vin.indexOf(root);        var vinleft = vin.slice(0,vinrootindex);        var vinright = vin.slice(vinrootindex+1,vin.length);        pre.shift();        var preleft = pre.slice(0,vinleft.length);        var preright = pre.slice(vinleft.length,pre.length);        result = {            val : root,            left : reConstructBinaryTree(preleft,vinleft),            right : reConstructBinaryTree(preright,vinright)        }    }    else if(pre.length===1) {        result={            val: pre[0],            left: null,            right: null        }    }        return result;}

 4. 重建二叉树

-*- coding:utf-8 -*-# 先序遍历特点：第一个值是根节点# 中序遍历特点：根节点左边都是左子树，右边都是右子树# 思路：# 1.首先根据根节点a将中序遍历划分为两部分，左边为左子树，右边为右子树# 2.使用递归，左右子树再次；；；#  最后合成一棵树class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass Solution:    def Re(self,pre,tin):        if not pre or not tin:            return None #要求返回的是二叉树，不是数组        root = TreeNode(pre.pop(0))        index = tin.index(root.val)        root.left = self.Re(pre, tin[:index])        root.right = self.Re(pre, tin[index+1:])        return root

 5. 二叉树的镜像

#交换所有非页节点的子节点-*- coding:utf -8 -*-class TreeNode:    def __init__(self,x):        self.value = x        self.left = None        self.right = Noneclass Solution:    def Mirror(self,root):        if not root:            return root        root.left, root.right = root.right, root.left        self.Mirror(root.left)        self.Mirror(root.right)        return root