Bfs

Leetcode513。左下のツリー値を検索（ツリーの最後の行で左端の値を検索）



Leetcode513 Find Bottom Left Tree Value



対象要件

二分木が与えられた場合、ツリーの最後の行で左端の値を見つけます。以下に示すように：
画像
画像

トピック分析

出力リーフノードの値については、シーケンストラバーサルにBFSを使用できますが、問題の難しさは、左端のリーフノード値をどのように判断（取得）するかです。 ？



A：実際、シーケンスをトラバースすると、各ノードはその子ノードをキューにプッシュします。左端のノードは各レイヤーの最初の要素であり、キューに配置されます。 現在のレイヤーインデックスのヘッド要素は0です（例：2、3レイヤー、インデックス0は2） 、i = 0の値を取る必要があるだけです。

メインコードc ++

/** * 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: int findBottomLeftValue(TreeNode* root) { queue<TreeNode*>q q.push(root) int res = 0 while(!q.empty()) { int size = q.size() for(int i=0 i<size++i) { TreeNode* temp = q.front() q.pop() if(i==0) res = temp->val if(temp->left) q.push(temp->left) if(temp->right) q.push(temp->right) } } return res } } // How do you know which point is the leftmost?