Hike News
Hike News

[Cracking the Coding Interview] Tree

本文总阅读量次

List of Depths: Given a binary tree, design an algorithm which creates a linked list of all the nodes
at each depth (e.g., if you have a tree with depth 0, you’ ll have 0 linked lists).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ListNode:
      def __init__(self, x):
          self.val = x
          self.next = None
  class TreeNode:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
class TreeLevel:
    def getTreeLevel(self, root, dep):
        
        s=ListNode(-1)
        p=s
        if dep<=0 or not root:
            return None
        if dep==1:
            p.next=ListNode(root.val)
            p=p.next
        else:
            self.getTreeLevel(root.left, dep-1)
            self.getTreeLevel(root.right, dep-1)
        return s.next

Check Balanced: Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  class TreeNode:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
class Checker:
    def checkBST(self, root):
        self.arr = []
        self.dfs(root)
        return self.arr == sorted(self.arr)
 
    def dfs(self, root):
        if not root:
            return
        self.dfs(root.left)
        self.arr.append(root.val)
        self.dfs(root.right)

Successor: Write an algorithm to find the “next” node (i .e ., in-order successor ) of a given node in a binary search tree. You may assume that each node has a link to its parent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  class TreeNode:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
class Successor:
    def findSucc(self, root, p):
        # write code here
        self.arr=[]
        self.dfs(root)
        return self.arr[self.arr.index(p)+1]
        
    def dfs(self,root):
        if not root:
            return 
        self.dfs(root.left)
        self.arr.append(root.val)
        self.dfs(root.right)

Paths with Sum: You are given a binary tree in which each node contains an integer value (which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TreeNode:
      def __init__(self, x):
          self.val = x
          self.left = None
          self.right = None
class Solution:
    
    def FindPath(self, root, expectNumber):

        res = []
        paths = self.dfs(root)
        return [a for a in paths if sum(a)==expectNumber]

    def dfs(self, root):
        if root is None: return []
        if not root.left and not root.right:
            return [[root.val]]

        paths = [[root.val] + path for path in self.dfs(root.left)]+[[root.val] + path for path in self.dfs(root.right)]

        return paths