classSolution{public:vector<vector<int>>verticalOrder(TreeNode*root){if(root==nullptr)return{};vector<int>range(2);getRange(root,range,0);// Get the leftmost and the rightmost x index.vector<vector<int>>ans(range[1]-range[0]+1);queue<pair<TreeNode*,int>>q{{{root,-range[0]}}};// (TreeNode, x)while(!q.empty()){constauto[node,x]=q.front();q.pop();ans[x].push_back(node->val);if(node->left)q.emplace(node->left,x-1);if(node->right)q.emplace(node->right,x+1);}returnans;}private:voidgetRange(TreeNode*root,vector<int>&range,intx){if(root==nullptr)return;range[0]=min(range[0],x);range[1]=max(range[1],x);getRange(root->left,range,x-1);getRange(root->right,range,x+1);}};
classSolution{publicList<List<Integer>>verticalOrder(TreeNoderoot){if(root==null)returnnewArrayList<>();List<List<Integer>>ans=newArrayList<>();Queue<Pair<TreeNode,Integer>>q=newArrayDeque<>();// (TreeNode, x)int[]range=newint[2];getRange(root,range,0);// Get the leftmost and the rightmost x index.for(inti=range[0];i<=range[1];++i)ans.add(newArrayList<>());q.offer(newPair<>(root,-range[0]));while(!q.isEmpty()){finalTreeNodenode=q.peek().getKey();finalintx=q.poll().getValue();ans.get(x).add(node.val);if(node.left!=null)q.offer(newPair<>(node.left,x-1));if(node.right!=null)q.offer(newPair<>(node.right,x+1));}returnans;}privatevoidgetRange(TreeNoderoot,int[]range,intx){if(root==null)return;range[0]=Math.min(range[0],x);range[1]=Math.max(range[1],x);getRange(root.left,range,x-1);getRange(root.right,range,x+1);}}
classSolution:defverticalOrder(self,root:TreeNode|None)->list[list[int]]:ifnotroot:return[]range_=[0]*2defgetRange(root:TreeNode|None,x:int)->None:ifnotroot:returnrange_[0]=min(range_[0],x)range_[1]=max(range_[1],x)getRange(root.left,x-1)getRange(root.right,x+1)getRange(root,0)# Get the leftmost and the rightmost x index.ans=[[]for_inrange(range_[1]-range_[0]+1)]q=collections.deque([(root,-range_[0])])# (TreeNode, x)whileq:node,x=q.popleft()ans[x].append(node.val)ifnode.left:q.append((node.left,x-1))ifnode.right:q.append((node.right,x+1))returnans
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! π