Interview Practice 11 – Greatest Distance Between Two Nodes in Binary Tree

9Question

Get the greatest distance between two nodes in a binary tree. Assume links between nodes are bidirectional. Distance is defined as the amount of nodes connected along the path linked two nodes. Write an algorithm to calculate distance between two nodes. Take the figure at the right, the greatest length should be 4.

Solution

Usual post-order recursive binary tree traversal should do the job. In this case, (obviously) the path must passes through the root. So we should do the following. Recursively return the max length (from left or right) to the parent, and make an exception for the root. The result is simply the sum of maxes from left and right.

Example

# node structure
class bst_node:
    left = None
    right = None
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

# join left and right max at root, literally
def get_max_len(root):
    left_max = depth_first_traversal(root.left)
    right_max = depth_first_traversal(root.right)
    return left_max + right_max

# a usual traversal, returning the max length begin
# from this node
def depth_first_traversal(node):
    if not node: return 0
    left_max = depth_first_traversal(node.left)
    right_max = depth_first_traversal(node.right)
    return max(left_max, right_max) + 1

# binary tree setup
node_12 = bst_node()
node_13 = bst_node()
node_05 = bst_node()
node_07 = bst_node(node_12, node_13)
node_09 = bst_node()
node_11 = bst_node()
node_06 = bst_node(node_05, node_07)
node_10 = bst_node(node_09, node_11)
node_08 = bst_node(node_06, node_10)

# answer should be 5
root = node_08
print get_max_len(root)
# node structure
class bst_node:
    left = None
    right = None
    left_max_dist = 0
    right_max_dist = 0

    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def max_dist(self):
        return max(self.left_max_dist, self.right_max_dist)

# calculate function
def calculate_max_len(node):

    # check node
    if not node: return 0

    # if left is not empty, then left is is the max + 1
    if node.left:
        calculate_max_len(node.left)
        node.left_max_dist = node.left.max_dist() + 1

    # if right is not empty, right is is the max + 1
    if node.right:
        calculate_max_len(node.right)
        node.right_max_dist = node.right.max_dist() + 1

    # return the max dist
    return node.left_max_dist + node.right_max_dist

# bst
node_12 = bst_node()
node_13 = bst_node()
node_5 = bst_node()
node_7 = bst_node(node_12, node_13)
node_9 = bst_node()
node_11 = bst_node()
node_6 = bst_node(node_5, node_7)
node_10 = bst_node(node_9, node_11)
node_8 = bst_node(node_6, node_10)

# answer should be 5
root = node_8
print calculate_max_len(root)
// 数据结构定义
struct NODE
{
     NODE* pLeft;            // 左子树
     NODE* pRight;          // 右子树
     int nMaxLeft;          // 左子树中的最长距离
     int nMaxRight;         // 右子树中的最长距离
     char chValue;        // 该节点的值
};

int nMaxLen = 0;

// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
{
     // 遍历到叶子节点,返回
     if(pRoot == NULL) {
          return;
     }
     // 如果左子树为空,那么该节点的左边最长距离为0
     if(pRoot -> pLeft == NULL) {
          pRoot -> nMaxLeft = 0;
     }
     // 如果右子树为空,那么该节点的右边最长距离为0
     if(pRoot -> pRight == NULL) {
          pRoot -> nMaxRight = 0;
     }
     // 如果左子树不为空,递归寻找左子树最长距离
     if(pRoot -> pLeft != NULL) {
          FindMaxLen(pRoot -> pLeft);
     }
     // 如果右子树不为空,递归寻找右子树最长距离
     if(pRoot -> pRight != NULL) {
          FindMaxLen(pRoot -> pRight);
     }
     // 计算左子树最长节点距离
     if(pRoot -> pLeft != NULL) {
          int nTempMax = 0;
          if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) {
               nTempMax = pRoot -> pLeft -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pLeft -> nMaxRight;
          }
          pRoot -> nMaxLeft = nTempMax + 1;
     }
     // 计算右子树最长节点距离
     if(pRoot -> pRight != NULL) {
          int nTempMax = 0;
          if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) {
               nTempMax = pRoot -> pRight -> nMaxLeft;
          }
          else {
               nTempMax = pRoot -> pRight -> nMaxRight;
          }
          pRoot -> nMaxRight = nTempMax + 1;
     }
     // 更新最长距离
     if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen) {
          nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
     }
 }
 //很明显,思路完全一样,但书上给的这段代码更规范!:)。
//定义一个结构体
struct NODE
{
    NODE* pLeft;
    NODE* pRight;
    int MaxLen;
    int MaxRgt;
};
NODE* pRoot;  //根节点
int MaxLength;

void traversal_MaxLen(NODE* pRoot) {
    if(pRoot == NULL) {
        return 0;
    };
    if(pRoot->pLeft == NULL) {
        pRoot->MaxLeft = 0;
    }
    // 若左子树不为空
    else {
        int TempLen = 0;
        // 左子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pLeft->MaxLeft > pRoot->pLeft->MaxRight) {
            TempLen+=pRoot->pLeft->MaxLeft;
        }
        else {
            TempLen+=pRoot->pLeft->MaxRight;
        }
        pRoot->nMaxLeft = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pLeft); // 此处,加上递归
    }

    if(pRoot->pRigth == NULL) {
        pRoot->MaxRight = 0;
    }
    // 若右子树不为空
    else {
        int TempLen = 0;
        // 右子树上的,某一节点,往左边大,还是往右边大
        if(pRoot->pRight->MaxLeft > pRoot->pRight->MaxRight) {
            TempLen+=pRoot->pRight->MaxLeft;
        }
        else {
            TempLen+=pRoot->pRight->MaxRight;
        }
        pRoot->MaxRight = TempLen + 1;
        traversal_MaxLen(NODE* pRoot->pRight); // 此处,加上递归
    }

    if(pRoot->MaxLeft + pRoot->MaxRight > 0) {
        MaxLength=pRoot->nMaxLeft + pRoot->MaxRight;
    }
}

Leave a Reply

%d bloggers like this: