03：树

算法面试其他篇

目录：

1.1 找到树中距离最大的两个结点

　　1、解题思路

　　　　　　1. 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。

　　　　　　    对于情况A来说，只需要知道左右子树的深度，然后加起来即可。

　　　　　　2. 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者

　　　　　　    对于情况B来说，需要知道左子树的最远距离，右子树的最远距离。

　　　　　　3. 只需要计算这两种情况的路径距离，并取其最大值，就是该二叉树的最大距离。

　　2、代码实现

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left    #左子树
        self.right=right  #右子树


class Solution(object):
    def diameterOfBinaryTree(self, root):
        if not root:
            return 0
        max_dia_left = self.diameterOfBinaryTree(root.left)      # 左子树的最远距离
        max_dia_right = self.diameterOfBinaryTree(root.right)    # 右子树的最远距离
        max_dia = max(self.get_depth(root.left) + self.get_depth(root.right), max_dia_left,max_dia_right)
        # 情况1：左右子树的深度，然后加起来    情况2：左右子树距离最远的那个
        return max_dia

    def get_depth(self, root):  # 计算以当前结点为根时，树的最大深度；
        if not root:
            return 0
        else:
            return max(1 + self.get_depth(root.left), 1 + self.get_depth(root.right))


if __name__=='__main__':
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    s = Solution()   #  DBACEGF
    print s.diameterOfBinaryTree(root)  # 5

　　　　　　

1.2 给定一个二叉树，原地将它展开为链表

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node:
    def __init__(self,value=None,left=None,right=None):
        self.value=value
        self.left=left    #左子树
        self.right=right  #右子树

class Solution(object):
    def flatten(self, root):
        if not root:
            return
        self.flatten(root.left)
        self.flatten(root.right)
        if not root.left:  # 如果当前节点没有左侧字节接返回上层调用，执行self.flatten(root.right),访问上层根节点的右子树
            return

        temp = root.right

        l = root.left  # 第一次找到的root是第一个有左子树的根节点，l是最左侧的叶子节点
        while l.right:  # 如果没有左节点的有右节点，那么一直找到最右侧节点复制给l
            l = l.right
        root.right = root.left
        l.right = temp

        root.left = None
        return root


if __name__=='__main__':
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    l = Solution().flatten(root)
    print l.value                 # D
    print l.right.value                 # B
    print l.right.right.value                 # A
    print l.right.right.right.value                 # C
    print l.right.right.right.right.value                 # E
    print l.right.right.right.right.right.value                 # G
    print l.right.right.right.right.right.right.value                 # F

　　　　

1111111111111