leetcode : Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   
2     3
 
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

思路：用两个stack<TreeNode*> in , s;

in : 记录当前的路径 p  , 和vector<int>path 相同，只不过一个记录的是 val ，一个记录点的指针。

s  : 记录每个节点的  p->right 

v2s : 将path转换称符合要求的string

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:string v2s(vector<int>a){
    const int len = a.size();
    string re = "";
    char *p = new char[500];
    for (int i = 0; i<len; i++){
        stringstream ss;    // 需要包含头文件  #include<sstream>
        string temp;
        ss << a[i];
        ss >> temp;
        re = re + temp;
        if (i != len - 1)
            re = re + "->";
    }
    return re;
}
vector<string> binaryTreePaths(TreeNode* root) {
    vector<int> path;
    vector<string> re;
    if (root == NULL) return re;
    TreeNode * p = root;
    stack<TreeNode*> in, s;
    while (p != NULL){
        if (p->left == NULL&&p->right == NULL){
            in.push(p);
            path.push_back(p->val);
            re.push_back(v2s(path));
            if (s.empty())
                return re;
            else {
　　　　　　　　　　// 通过while循环，查找下一个需要遍历的点
                while (!in.empty() && !s.empty() && (in.top())->right != s.top()){
                    in.pop();
                    path.erase(path.end()-1);
                }
                p = s.top();
                s.pop();
            }
        }
        else if (p->left == NULL&&p->right != NULL){
            path.push_back(p->val);
            in.push(p);
            p = p->right;
        }
        else if (p->left != NULL&&p->right == NULL){
            path.push_back(p->val);
            in.push(p);
            p = p->left;
        }
        else{
            path.push_back(p->val);
            in.push(p);
            s.push(p->right);
            p = p->left;
        }
    }
    return re;
}
};

 另一道相似题目

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。

给定二叉树的根节点root，请返回所求距离。

思路：只需要将保存的路径进行比较，相同的去掉然后相加，就能算出路径长度。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Tree {
public:
int getDis(TreeNode* root) {
	// write code here
	stack<TreeNode*> max, min;
	int m = INT_MIN, n = INT_MAX, re = 0;
	stack<TreeNode*> in, s;
	TreeNode *p = root;
	while (p != NULL){
		if (p->left == NULL&&p->right == NULL){
			in.push(p);
			if (p->val > m){
				max = in;
				m = p->val;
			}
			if (p->val < n){
				min = in;
				n = p->val;
			}
			while (!in.empty() && !s.empty() && (in.top())->right != s.top()){
				in.pop();
			}
			if (s.empty())
				break;
			else {
				p = s.top();
				s.pop();
			}
		}
		else if (p->left == NULL&&p->right != NULL){
			in.push(p);
			p = p->right;
		}
		else if (p->left != NULL&&p->right == NULL){
			in.push(p);
			p = p->left;
		}
		else {
			in.push(p);
			s.push(p->right);
			p = p->left;
		}
	}
	stack<TreeNode*> t1, t2;
	while (!max.empty()){
		t1.push(max.top());
		max.pop();
	}
	while (!min.empty()){
		t2.push(min.top());
		min.pop();
	}
	while (!t1.empty() && !t2.empty()){
		if (t1.top() != t2.top())
			break;
		else
			t1.pop(); t2.pop();
	}
	re = re + t1.size() + t2.size();
	return re;
}
};