编程之美 求二叉树中节点的最大距离 非递归

The basic program is to get the height of a binary tree. We could use BFS to realize that. So the result is :

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;


class TreeNode {
public:
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void display(TreeNode* root, int col = 0) {
  if(root == 0)    
    return;
  display(root->right, col + 1);
  for(int i = 0; i < col; ++i)   
    std::cout<<"| ";
  cout<<"|"<<root->val<<std::endl;
  display(root->left, col + 1);
}
int getHeight(TreeNode* root) {
  int cnt = 0, i, j, cur = 0, next = 1;
  vector<TreeNode*> layers[2];
  layers[cur].push_back(root);
  while (!layers[cur].empty()) {
    ++cnt;
    for (i = 0; i < layers[cur].size(); ++i) {
      if (layers[cur][i]->left)
        layers[next].push_back(layers[cur][i]->left);
      if (layers[cur][i]->right)
        layers[next].push_back(layers[cur][i]->right);
    } 
    layers[cur].clear();
    cur = !cur;
    next = !next;
  }
  return cnt;
}
int getMaxDistance(TreeNode* root) {
  int lcount = 0, rcount = 0, res = 0;
  if (root == NULL)
    return 0;
  while (root->left && !root->right || !root->left && root->right) {
    ++res;
    if (root->left)
      root = root->left;
    else
      root = root->right;
  }
  if (root->left && root->right) {
    lcount = getHeight(root->left);
    rcount = getHeight(root->right);
  }
  return res + lcount + rcount;
}
int main() {

  TreeNode *root = new TreeNode(0);
  root->left = new TreeNode(1);
  root->right = new TreeNode(2);
  root->left->left = new TreeNode(3);
  root->left->right = new TreeNode(4);
  root->right->left = new TreeNode(5);
  root->right->right = new TreeNode(6);
  root->right->right->right = new TreeNode(7);

  display(root);
  int res = getMaxDistance(root);

  return 0;
}

编程之美 求二叉树中节点的最大距离 非递归,布布扣,bubuko.com

编程之美 求二叉树中节点的最大距离 非递归

原文：http://blog.csdn.net/taoqick/article/details/22691983