LeetCode-二叉树

Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

LeetCode109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

class Solution:
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        p = head
        length = 0
        while p:
            p = p.next
            length += 1
        head = [head]
        root = self.sorted_list2bst(head,0,length-1)
        return root
    def sorted_list2bst(self,head,start,end):
        if start>end: return None
        
        m = (start+end)>>1
        left = self.sorted_list2bst(head,start,m-1)
        root = TreeNode(head[0].val)
        root.left = left
        head[0] = head[0].next
        root.right = self.sorted_list2bst(head,m+1,end)
        
        return root

LeetCode114. 二叉树展开为链表

给定一个二叉树，原地将它展开为链表。
前序遍历

class Solution:
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        stack = []
        if root is None: return
        stack.append(root)
        pre = None
        while stack:
            p = stack.pop()
            if pre:
                pre.left = None
                pre.right = p
            if p.right: stack.append(p.right)
            if p.left: stack.append(p.left)
            # p.right = None
            pre = p
        return

LeetCode116. 填充同一层的兄弟节点

给定一个二叉树填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

初始状态下，所有 next 指针都被设置为 NULL。

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if root is None: return
        start = root
        while start.left:
            cur = start
            while cur:
                cur.left.next = cur.right
                if cur.next:
                    cur.right.next = cur.next.left
                cur = cur.next
            start = start.left
        return

LeetCode124. 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = [-10**6]
        self.pathsum_core(root,res)
        return res[0]
        
    def pathsum_core(self,root,res):
        if not root: return 0
        left = max(self.pathsum_core(root.left,res),0)
        right = max(self.pathsum_core(root.right,res),0)
        # 计算当前节点作为根节点时得到的最大和
        res[0] = max(res[0],left + right + root.val)
        # 当前节点作为一个左（右）子节点返回的时候，智能包含左子树或者右子树的返回值中的一个。
        return max(left,right)+root.val

LeetCode236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if (not root) or root==p or root==q: return root
        
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        
        if left and right: return root
        if left:
            return left
        else:
            return right