博客

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1

示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:

基本思路： 翻转二叉树的层序遍历。

1. 一个二叉树的层序遍历是每一层从左向右进行遍历。（不明白的同学可以百度一下）。
2. 将二叉树数的层序遍历翻转一下即可。

class Solution {
public:
	int findBottomLeftValue(TreeNode* root) {
		vector<TreeNode*> Temp;
		Temp.push_back(root);
		int End = 0;
		while (End!=Temp.size()) {
			if (Temp[End]->right != NULL) {
				Temp.push_back(Temp[End]->right);
			}
			if (Temp[End]->left != NULL) {
				Temp.push_back(Temp[End]->left);
			}


			/* 这么写是二叉树的层序遍历，先遍历左节点，再遍历右节点
			if (Temp[End]->left != NULL) {
				Temp.push_back(Temp[End]->left);
			}
			if (Temp[End]->right != NULL) {
				Temp.push_back(Temp[End]->right);
			}
			*/

			End++;
		}
		return Temp[Temp.size() - 1]->val;
	}
};